HDOJ1114(完全背包)

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=0x30303030;
const int SIZE=10000+16;
int w[SIZE];
int v[SIZE];
int dp[SIZE];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int E,F;
        scanf("%d %d",&E,&F);
        int vol=F-E;
        
        int N;
        scanf("%d",&N);
        
        for(int i=0;i<N;i++)
        {
            scanf("%d %d",&v[i], &w[i]);
        }    
        
        memset(dp,INF,sizeof(dp));
        dp[0]=0;
        
        for(int i=0;i<N;i++)
            for(int j=w[i];j<=vol;j++)
                if(dp[j]>dp[j-w[i]]+v[i])
                    dp[j]=dp[j-w[i]]+v[i];
        
        if(dp[vol]==INF)
            printf("This is impossible.
");
        else
            printf("The minimum amount of money in the piggy-bank is %d.
",dp[vol]);
        
    }
    
    return 0;
}