1267：【例9.11】01背包问题

时间限制: 1000 ms 内存限制: 65536 KB【题目描述】一个旅行者有一个最多能装 M 公斤的背包现在有 n 件物品它们的重量分别是W1W2...,Wn,它们的价值分别为C1,C2,...,Cn求旅行者能获得最大总价值。【输入】第一行两个整数M(背包容量M≤200)和N(物品数量N≤30)第2..N1行每行二个整数WiCi表示每个物品的重量和价值。【输出】仅一行一个数表示最大总价值。【输入样例】10 4 2 1 3 3 4 5 7 9【输出样例】12#include bits/stdc.h using namespace std; int m,n; int w[201],c[31]; int D1(int mx){//普通版 未空间优化 int dp[31][201]; memset(dp,0,sizeof(dp)); for(int i1;in;i){ for(int j1;jmx;j){ dp[i][j]dp[i-1][j];//第i个物品不取 if(jw[i])dp[i][j]max(dp[i][j],dp[i-1][j-w[i]]c[i]);//取第i个物品 } } return dp[n][mx]; } int D2(int mx){//空间优化 int a[201];//用a[j] 替换原来的 dp[i-1][j] int b[201];//用b[j] 替换原来的 dp[i][j] memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i1;in;i){ for(int j1;jmx;j){ b[j]a[j];//第i个物品不取 if(jw[i])b[j]max(b[j],a[j-w[i]]c[i]);//取第i个物品 } for(int j1;jmx;j)a[j]b[j]; } return b[mx]; } int D3(int mx){//空间优化 int b[201];//用b[j] 替换原来的 a[j] 和 b[j] memset(b,0,sizeof(b)); for(int i1;in;i){ //因为要用去 b[j-w[i]] 的数据所以要倒序遍历 正序的话新数据就覆盖之前的数据了 for(int jmx;j0;j--){ //b[j]b[j];//第i个物品不取 if(jw[i])b[j]max(b[j],b[j-w[i]]c[i]);//取第i个物品 } } return b[mx]; } int factorial(int i,int mx){//动态规划 递归写法 if(i0 || mx0)return 0; int xxfactorial(i-1,mx);//第i个物品不取 if(mxw[i])xxmax(xx,factorial(i-1,mx-w[i])c[i]);//取第i个物品 return xx; } int main(int argc, char** argv) { scanf(%d%d,m,n); for(int i1;in;i){ scanf(%d%d,w[i],c[i]); } //printf(%d,D1(m));//普通版 未空间优化 //printf(%d,D2(m));//空间优化 //printf(%d,D3(m));//空间优化 printf(%d,factorial(n,m));//动态规划 递归写法 return 0; }