揭阳自助建站软件,手机微信网站开发教程,徐州数据网站建设介绍,wordpress电影站群题意#xff1a; 给出一个存钱罐的空罐时的质量和装了钱之后的质量#xff0c;再给出一些硬币的质量和相应的价值#xff0c;问存钱罐里的钱最少可能为多少。 这道题就是完全背包的问题#xff0c;注意初始化。 完全背包与01背包不同的是第二次遍历的时候要顺序而已。 初始…题意 给出一个存钱罐的空罐时的质量和装了钱之后的质量再给出一些硬币的质量和相应的价值问存钱罐里的钱最少可能为多少。 这道题就是完全背包的问题注意初始化。 完全背包与01背包不同的是第二次遍历的时候要顺序而已。 初始化这道题要求背包恰好装满而且要求的值尽量少所以dp[0]0;其余设为无穷大。 1.若没有要求恰好装满则全为0. 2.若要求的值尽量大则dp[0]0;其余为无穷小。 1 #includecstdio2 #includealgorithm3 using namespace std;4 const int maxn1000010;5 const int inf0x3f3f3f3f;6 int dp[maxn];7 int main()8 {9 int test;
10 scanf(%d,test);
11 while(test--)
12 {
13 int e,f;
14 scanf(%d%d,e,f);
15 int mf-e;
16 dp[0]0;
17 for(int i1;im;i)
18 dp[i]inf;
19 int p,w,n;
20 scanf(%d,n);
21 for(int i1;in;i)
22 {
23 scanf(%d%d,p,w);
24 for(int jw;jm;j)
25 {
26 dp[j]min(dp[j],dp[j-w]p);
27 }
28 }
29 if(dp[m]inf)
30 printf(This is impossible.\n);
31 else
32 printf(The minimum amount of money in the piggy-bank is %d.\n,dp[m]);
33 }
34 return 0;
35 } View Code 转载于:https://www.cnblogs.com/-maybe/p/4380867.html
