HDU 1114 Piggy-Bank

传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1114

本题大意：

告诉你空的存钱罐的重量和装满存钱罐的重量。然后告诉你有多少中硬币。并且告诉你每种硬币的重量和价值。

问你存钱罐中最少装了多少钱。这就是一个完全背包问题。

实现代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN=100000;
const int INF=1<<30;


int main(){
    int T;
    int dp[MAXN];
    int w[MAXN],v[MAXN];

    scanf("%d",&T);
    while(T--){
        int E,F,W;
        scanf("%d%d",&E,&F);
        W=F-E;
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d%d",&v[i],&w[i]);

        for(int i=0;i<=W;i++)
            dp[i]=INF;
        dp[0]=0;

        for(int i=0;i<n;i++)
            for(int j=w[i];j<=W;j++)
                dp[j]=min(dp[j],dp[j-w[i]]+v[i]);

        if(dp[W]==INF)
            printf("This is impossible.
");
        else
            printf("The minimum amount of money in the piggy-bank is %d.
",dp[W]);

    }

}