苹果
时间限制：3000 ms | 内存限制：65535 KB
难度：3
- 描述
-
ctest有n个苹果，要将它放入容量为v的背包。给出第i个苹果的大小和价钱，求出能放入背包的苹果的总价钱最大值。
- 输入
- 有多组测试数据，每组测试数据第一行为2个正整数，分别代表苹果的个数n和背包的容量v，n、v同时为0时结束测试，此时不输出。接下来的n行，每行2个正整数，用空格隔开，分别代表苹果的大小c和价钱w。所有输入数字的范围大于等于0，小于等于1000。
- 输出
- 对每组测试数据输出一个整数，代表能放入背包的苹果的总价值。
- 样例输入
-
3 3 1 1 2 1 3 1 0 0
- 样例输出
-
2
-
来源
动态规划中背包的经典问题，以前做过一次了，以前做这种题目的时候，运用的思想是贪心，贪心也可以得到解，但是有时候这个解不是最优的；
运用动态规划思想把这道题在做一次；参考了背包九讲（真的讲的不错，以前有些不懂的地方，现在理解更深了）
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物 品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
上面的内容引用了背包九讲中的第一讲；这种解法在时间复杂度上是n(nv),比较高效了，但是在空间复杂度上还可以优化；
下面是用最简单的方法写的：空间复杂度还可以优化；动态规划写的程序一般都比较精简，但是就是理解其中的状态表达式；
#include <cstdio> #include <cstring> #define max(a,b) a>b?a:b const int maxn=1001; int c[maxn],w[maxn],dp[maxn][maxn]; int main() { int n,v,i,j; while(scanf("%d%d",&n,&v)&&n&&v) { memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) scanf("%d%d",&c[i],&w[i]); for(i=1;i<=n;i++) for(j=1;j<=v;j++) { if(j<c[i]) dp[i][j]=dp[i-1][j];//状态表达式 else dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]); } printf("%d\n",dp[n][v]); } }
优化内存的写法，把dp的二维数组换成一维数组，不用数组储存背包的值；用一维数组解背包问题，在后面很多地方也会用到，一定要掌握这种用法；#include<cstdio> #include<cstring> #define max(a,b) a>b?a:b const int maxn=1001; int dp[maxn]; int main() { int n,v,i,j,c,w; while(scanf("%d%d",&n,&v)&&n&&v) { memset(dp,0,sizeof(dp));//初始化 for(i=1;i<=n;i++) { scanf("%d%d",&c,&w); for(j=v;j>=c;j--) dp[j]=max(dp[j],dp[j-c]+w);//递推关系 } printf("%d\n",dp[v]); } return 0; }