描述： n个重量价值为wi,vi的物品，从这些物品中挑出重量不超过w的物品，求挑选方案中价值和最大值
1=<n<=100
1=<wi,vi<=100
1=<=W<=10000
输入：4
2 3 1 2 3 4 2 2
5
输出：
7
#include<iostream> using namespace std; int const maxn=1000; int n,W; int w[maxn],v[maxn]; int rec(int i,int j){ int res; if(i==n){ res=0; }else if(j<w[i]){//无法挑选 res=rec(i+1,j); }else { res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]); } return res; } int main() { cin>>n; int i; for(i=0;i<n;i++) cin>>w[i]>>v[i]; cin>>W; // rec(0,W); cout<< rec(0,W)<<endl; }
优化后的代码：dp[][] 记录选还是不选时候的状态
//记忆化数组，优化 #include<iostream> using namespace std; int const maxn=1000; int n,W; int w[maxn],v[maxn]; int dp[maxn][maxn]; int rec(int i,int j){ if(dp[i][j]) return dp[i][j]; int res; if(i==n){ res=0; }else if(j<w[i]){//无法挑选 res=rec(i+1,j); }else { res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]); } return dp[i][j]=res; } int main() { cin>>n; int i; for(i=0;i<n;i++) cin>>w[i]>>v[i]; cin>>W; // rec(0,W); cout<< rec(0,W)<<endl; }
原文：https://www.cnblogs.com/helloworld2019/p/10585798.html
