Piggy Bank

  完全背包的经典问题，只要把状态转移方程的max改为min，同时将dp[0]设为0，其余则设为INF即可( 因为要求是否能装满 )

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3fffffff
using namespace std;
int val[510];
int w[510];
int dp[10010];
void init()
{
    for(int i=0;i<10010;i++)
        dp[i]=INF;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {    
        init();dp[0]=0;
        mst(val,0);mst(w,0);
        int empty,with_coin;
        cin>>empty>>with_coin;
        int vtot=with_coin-empty;
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>val[i]>>w[i];
        for(int i=0;i<n;i++)
            for(int j=w[i];j<=vtot;j++)
                dp[j]=min(dp[j],dp[j-w[i]]+val[i]);
        if(dp[vtot]==INF)
            cout<<"This is impossible."<<endl;
        else
            cout<<"The minimum amount of money in the piggy-bank is "<<dp[vtot]<<"."<<endl;
    }
    return 0;
}