HDU 1114 Piggy-Bank

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1114

分析：每个物品可以取无限个，完全背包问题，要求装满，所以dp[0]=0,其余为INF；

 1 #include<iostream>
 2 #include<sstream>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<string>
 6 #include<cstring>
 7 #include<algorithm>
 8 #include<functional>
 9 #include<iomanip>
10 #include<numeric>
11 #include<cmath>
12 #include<queue>
13 #include<vector>
14 #include<set>
15 #include<cctype>
16 #define PI acos(-1.0)
17 const int INF = 0x3f3f3f3f;
18 const int NINF = -INF - 1;
19 const int maxn = 1e4 + 5;
20 typedef long long ll;
21 using namespace std;
22 int cost[505], weight[505];
23 int dp[maxn];
24 int main()
25 {
26     int T;
27     scanf("%d", &T);
28     while (T--)
29     {
30         int E, F;
31         scanf("%d%d", &E, &F);
32         int n;
33         scanf("%d", &n);
34         for (int i = 0; i < n; ++i)
35             scanf("%d%d", &cost[i], &weight[i]);
36         int ans = F - E;
37         for (int i = 0; i <= ans; ++i)
38             dp[i] = INF;
39         dp[0] = 0;
40         for (int i = 0; i < n; ++i)
41         {
42             for (int j = weight[i]; j <= ans; ++j)
43             {
44                 dp[j] = min(dp[j], dp[j - weight[i]] + cost[i]);
45                 //cout << j << ' ' << dp[j] << endl;
46             }
47         }
48         if (dp[ans] == INF) printf("This is impossible.
");
49         else printf("The minimum amount of money in the piggy-bank is %d.
", dp[ans]);
50     }
51     return 0;
52 }