辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。
为此，他想拜附近最有威望的医师为师。
医师为了判断他的资质，给他出了一个难题。
如果你是辰辰，你能完成这个任务吗？
7037110069112输出样例：3分析：
每次面临两种选择，选和不选、
代码：
二维代码：
1#include23usingnamespacestd;45constintN=1010;67intn,m;8intv[N],w[N];9intf[N][N];//含义：选到第i个物品，当前体积为j的情况下，价值最大1011intmain()12{13cin>>m>>n;14for(inti=1;i<=n;i++)cin>>v[i]>>w[i];1516for(inti=1;i<=n;i++)17{18for(intj=0;j<=m;j++)19{20f[i][j]=f[i-1][j];21if(j-v[i]>=0)22f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);23}24}2526cout<1#include23usingnamespacestd;45constintN=1010;67intn,m;8intv[N],w[N];9intf[N][N];//含义：选到第i个物品，当前体积为j的情况下，价值最大1011intmain()12{13cin>>m>>n;14for(inti=1;i<=n;i++)cin>>v[i]>>w[i];1516for(inti=1;i<=n;i++)17{18for(intj=0;j<=m;j++)19f[i][j]=f[i-1][j];//不选当前第i个物品，那么f维护的最大值这个属性，就是前面的值20for(intj=0;j<=m;j++)21if(j-v[i]>=0)22f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);2324}2526cout<1#include23usingnamespacestd;45constintN=1010;67intn,m;8intv[N],w[N];9intf[2][N];//含义：选到第i个物品，当前体积为j的情况下，价值最大1011intmain()12{13cin>>m>>n;14for(inti=1;i<=n;i++)cin>>v[i]>>w[i];1516for(inti=1;i<=n;i++)17{18for(intj=0;j<=m;j++)19f[i&1][j]=f[(i-1)&1][j];//不选当前第i个物品，那么f维护的最大值这个属性，就是前面的值20for(intj=0;j<=m;j++)21if(j-v[i]>=0)22f[i&1][j]=max(f[i&1][j],f[(i-1)&1][j-v[i]]+w[i]);2324}2526cout<1#include23usingnamespacestd;45constintN=1010;67intn,m;8intv[N],w[N];9intf[N];//含义：选到第i个物品，当前体积为j的情况下，价值最大1011intmain()12{13cin>>m>>n;14for(inti=1;i<=n;i++)cin>>v[i]>>w[i];1516for(inti=1;i<=n;i++)17for(intj=m;j>=v[i];j--)18f[j]=max(f[j],f[j-v[i]]+w[i]);19//j~m为当前的第i个物品，也就是第i层，而第i层，则是由1~j-1，由i-1层决定的。20cout<题目：
有一个箱子容量为V，同时有n个物品，每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
第一行是一个整数V，表示箱子容量。
第二行是一个整数n，表示物品数。
接下来n行，每行一个正整数（不超过10000），分别表示这n个物品的各自体积。
一个整数，表示箱子剩余空间。
2468312797输出样例：0分析：
还是一个0/1背包问题，这里的物品体积和价值都是我们的物品体积，然后每个物品只能选择一个，要在m体积内拼出一个最大体积，这个体积一定小于m
二维写法：
1#include23usingnamespacestd;45constintN=40,M=20010;67intn,m;8inta[N];9intf[N][M];1011intmain()12{13cin>>m>>n;14for(inti=1;i<=n;i++)cin>>a[i];1516for(inti=1;i<=n;i++)17{18for(intj=0;j<=m;j++)19f[i][j]=f[i-1][j];20for(intj=0;j<=m;j++)21if(j-a[i]>=0)22f[i][j]=max(f[i][j],f[i-1][j-a[i]]+a[i]);2324}2526cout<1#include23usingnamespacestd;45constintN=40,M=20010;67intn,m;8inta[N];9intf[M];1011intmain()12{13cin>>m>>n;1415for(inti=1;i<=n;i++)16{17intx;cin>>x;18for(intj=m;j>=x;j--)19f[j]=max(f[j],f[j-x]+x);20}2122cout<宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。
小智也想收服其中的一些小精灵。
然而，野生的小精灵并不那么容易被收服。
对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。
当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
当小智的精灵球用完时，狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。
如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。
小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。
请问，小智该如何选择收服哪些小精灵以达到他的目标呢？
输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。
输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
101005710240250120420输出样例1：330输入样例2：10100581101210201052001110输出样例2：0100分析：
这一题同样还是0/1背包的模型，变化的唯一地方就在于原来的背包容量由模型中的一个，到现在变成了两个，限制多加了一维，但是还是可以按照0/1被包的方式直接套路出来的。
三位滚动数组（第二问一直不对，没搞好呢）：
1#include23usingnamespacestd;45constintN=1010,M=510,K=110;67intn,m,k;//精灵球的数量，皮卡丘的体积，精灵的数量8intf[2][N][M];910intmain()11{12cin>>n>>m>>k;1314for(inti=0;i>v1>>v2;17for(intj=0;j<=n;j++)18for(intt=0;t<=m-1;t++)19f[i&1][j][t]=f[(i-1)&1][j][t];20//如果是等于m的话，说明体力恰好消耗完，这就很亏哦，因为当体力为0的时候，认为捕获失败21for(intj=0;j<=n;j++)22for(intt=0;t<=m-1;t++)23if(j-v1>=0&&t-v2>=0)24f[i&1][j][t]=max(f[i&1][j][t],f[(i-1)&1][j-v1][t-v2]+1);25}2627cout<0&&f[1][n][t-1]==f[1][n][m-1])t--;31ints=m-1;32while(s>0&&f[0][n][s-1]==f[0][n][m-1])s--;33cout<1#include23usingnamespacestd;45constintN=1010,M=510,K=110;67intn,m,k;//精灵球的数量，皮卡丘的体积，精灵的数量8intv1[K],v2[K];9intf[N][M];1011intmain()12{13cin>>n>>m>>k;14for(inti=1;i<=k;i++)cin>>v1[i]>>v2[i];1516for(inti=1;i<=k;i++)17{18for(intj=n;j>=v1[i];j--)19for(intt=m-1;t>=v2[i];t--)20f[j][t]=max(f[j][t],f[j-v1[i]][t-v2[i]]+1);21}2223cout<0&&f[n][t-1]==f[n][m-1])t--;26cout<包含一个整数，表示可选方案数。
441122输出样例：3分析：
还是0/1背包的模板，这次我们不是求得最值，而是求的方案数，这是需要累加的。
1//这种方案数的题目，在我印象中似乎是需要讲边界设置一下的，保证答案只能从一个起点开始2#include34usingnamespacestd;56constintN=110,M=10010;78intn,m;9intf[M];1011intmain()12{13cin>>n>>m;1415f[0]=1;//边界，只有0可以给我们贡献16for(inti=1;i<=n;i++)17{18intx;cin>>x;19for(intj=m;j>=x;j--)20f[j]+=f[j-x];21}2223cout<小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。
问小明有多少种买书方案？（每种书可购买多本）
一个整数n，代表总共钱数。
一个整数，代表选择方案种数。
20输出样例1：2输入样例2：15输出样例2：0输入样例3：0输出样例3：1分析：
注意这题和上一题的区别，上一题是从n个物品中选择若干个的方案数，而这一题是给定几个物品，每个物品都有无限个可以选择。
这显然是一个完全背包的问题。
1//还是一个求方案数的题目，不要忘记初始化f[0]=1;2//这是一个完全背包问题，每个物品都可以选择无数次3#include45usingnamespacestd;67constintN=1010;89intn;10inta[4]={10,20,50,100};11intf[N];1213intmain()14{15cin>>n;1617f[0]=1;18for(inti=0;i<4;i++)19for(intj=a[i];j<=n;j++)20f[j]+=f[j-a[i]];2122cout<给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。
第一行，包含两个整数n和m。
接下来n行，每行包含一个整数，表示一种货币的面值。
共一行，包含一个整数，表示方案数。
310125输出样例：10分析：
显然这是一个完全背包求方案数的题目，注意开longlong了
1//n种货币，可选无数次，显然是一个完全背包问题2#include34usingnamespacestd;56typedeflonglongll;7constintN=3010;89intn,m;10llf[N];1112intmain()13{14cin>>n>>m;1516f[0]=1;17while(n--)18{19intx;cin>>x;20for(inti=x;i<=m;i++)21f[i]+=f[i-x];22}2324cout<现在网友们打算简化一下货币系统。
2431910651129131917输出样例：25分析：
很显然还是一个完全背包，这次我们可以给货币价值按升序排序，然后判断前面的是否可以表示后面的就OK了。
1//完全背包，思路是，给他们排个序，如果前面能表示后边的，那就pass掉2#include3#include4#include5#include67usingnamespacestd;89constintN=30010;1011intn;12inta[N];13boolf[N];14intcnt;15voidwork()16{17cnt=0;18memset(f,0,sizeoff);19cin>>n;2021for(inti=0;i>a[i];2223sort(a,a+n);2425f[0]=1;26for(inti=0;i>T;39while(T--)40{41work();42}4344return0;45}
