1267：【例9.11】01背包问题
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn，求旅行者能获得最大总价值。
【输入】
第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；
第2..N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。
【输入样例】
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 i=1;i<=n;i++){ for(int j=1;j<=mx;j++){ dp[i][j]=dp[i-1][j];//第i个物品不取 if(j>=w[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 i=1;i<=n;i++){ for(int j=1;j<=mx;j++){ b[j]=a[j];//第i个物品不取 if(j>=w[i])b[j]=max(b[j],a[j-w[i]]+c[i]);//取第i个物品 } for(int j=1;j<=mx;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 i=1;i<=n;i++){ //因为要用去 b[j-w[i]] 的数据，所以要倒序遍历 ，正序的话新数据就覆盖之前的数据了 for(int j=mx;j>=0;j--){ //b[j]=b[j];//第i个物品不取 if(j>=w[i])b[j]=max(b[j],b[j-w[i]]+c[i]);//取第i个物品 } } return b[mx]; } int factorial(int i,int mx){//动态规划 递归写法 if(i==0 || mx==0)return 0; int xx=factorial(i-1,mx);//第i个物品不取 if(mx>=w[i])xx=max(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 i=1;i<=n;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; }