01背包，HDU 1114 iggy-Bank(完全背包)

2023-11-07 阅读 12 评论 0

摘要：水給出小豬錢罐的重量和裝滿錢后的重量，然后是幾組數據，每組數據包括每種錢幣的價值與重量要求出重量最少能裝滿錢罐時的最大價值 1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdlib> 5 #include&l

水

給出小豬錢罐的重量和裝滿錢后的重量，然后是幾組數據，每組數據包括每種錢幣的價值與重量

要求出重量最少能裝滿錢罐時的最大價值

 1 #include<iostream>
 2 #include<string>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 #include<cstdio>
 6 #include<set>
 7 #include<map>
 8 #include<vector>
 9 #include<cstring>
10 #include<stack>
11 #include<cmath>
12 #include<queue>
13 #include <bits/stdc++.h>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define ll long long
17 #define clc(a,b) memset(a,b,sizeof(a))
18 const int maxn=10010;
19 int dp[maxn];
20 int t;
21 int w,W,q;
22 int val[maxn],wei[maxn];
23 
24 int main()
25 {
26 //    freopen("in.txt","r",stdin);
27     scanf("%d",&t);
28     while(t--)
29     {
30         scanf("%d%d",&w,&W);
31         int tot=W-w;
32         scanf("%d",&q);
33         for(int i=0; i<q; i++)
34             scanf("%d%d",&val[i],&wei[i]);
35         for(int i=0;i<=tot;i++)
36             dp[i]=10000000;
37         //cout<<dp[0]<<endl;
38         dp[0]=0;
39         for(int i=0; i<q; i++)
40         {
41             for(int j=wei[i]; j<=tot; j++)
42             {
43                 dp[j]=min(dp[j],dp[j-wei[i]]+val[i]);
44             }
45         }
46         if(dp[tot]==10000000)
47             printf("This is impossible.\n");
48         else
49             printf("The minimum amount of money in the piggy-bank is %d.\n",dp[tot]);
50     }
51     return 0;
52 }