有n个重量和价值分别为wi,vi的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值
/** *首先动态记录第i个物品，和总重量小于j的部分 *并且将已经接受过的记录动态的保存在记忆化数组中 */ #include<stdio.h> #include<string.h> int N,W; int w[100],v[100]; //使用记忆化数组 int dp[100][100]; int max(int n,int m){ return n>m?n:m; } //从第i个物品开始挑选总重小于j的部分 int rec(int i,int j){ //如果当前位置存入数据，则直接返回该数据 if(dp[i][j]>=0) return dp[i][j]; //记录当前物品重量 int res; //当最后一个物品选择完成之后,可以添加的重量为0 if(i==N) res=0; //如果当前物品重量大于可添加的重量，当前物品不可以选择 else if(w[i]>j) 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(){ while(scanf("%d%d",&N,&W)==2){ memset(dp,-1,sizeof(dp)); for(int i=0;i<N;i++) scanf("%d%d",&w[i],&v[i]); printf("%d ",rec(0,W)); } return 0; } /************************************************第2种写法，递推表达式****************************************************/ #include<stdio.h> #include<string.h> int N,W; int v[100],w[100]; //dp为协助数组 int dp[100][100]; int max(int n,int m){ return n>m?n:m; } void rec(){ //从最后一个背包开始选择 //利用 i表示第i个背包 for(int i=N-1;i>=0;i--) //j表示,总重量小于j的部分 for(int j=0;j<=W;j++){ if(j<w[i]) dp[i][j]=dp[i+1][j]; else{ dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]); } } printf("%d ",dp[0][W]); } int main(){ while(scanf("%d%d",&N,&W)==2){ memset(dp,-1,sizeof(dp)); for(int i=0;i<N;i++) scanf("%d%d",&w[i],&v[i]); rec(); } return 0; }