又见01背包
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
有n个重量和价值分别为wi 和 vi 的 物品，从这些物品中选择总重量不超过 W
的物品，求所有挑选方案中物品价值总和的最大值。
1 <= n <=100
1 <= wi <= 10^7
1 <= vi <= 100
1 <= W <= 10^9
输入多组测试数据。每组测试数据第一行输入，n 和 W ，接下来有n行，每行输入两个数，代表第i个物品的wi 和 vi。输出满足题意的最大价值，每组测试数据占一行。样例输入4 52 31 23 42 2样例输出7一开始做这道题真心卡死，后来看别人题解才懂。。。把质量和价值互换就可以解出来，做过这道题后才发现自己的思维真心不给力，看来以后做题要用多种方法ac。/*01背包状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) 本题数据太坑，需要的内存过大，所以上面的方程是行不通的(亲身经历3次…)。 我们需要换个思路：基本方程里dp[i][j]记录的是i个物品装进重量为j的背包里的最大价值，我们可以让dp[i][j]记录i个物品价值和为j时的最小质量，相同价值肯定选择所需重量最少的。 我们只需要找到在小于或等于总质量的情况下的最大价值j即可状态转移方程：dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i]) 且有dp[i][j]<=W总重*/#include<stdio.h>#include<stdlib.h>#include<string.h>#include<algorithm>#define min(a,b)(a<b?a:b)#define max 1000 using namespace std;int dp[max];int w[110],v[110];int main(){int n,W,i,j;int sumv;//所有物品价值和while(scanf("%d%d",&n,&W)!=EOF){sumv=0;memset(dp,0x3f,sizeof(dp));//思路感觉行得通，但运行就是不对，，后来才明白一开始要初始化数组无穷大dp[0]=0;for(i=0;i<n;i++){scanf("%d%d",&w[i],&v[i]);sumv+=v[i];//记录所有物品价值和}for(i=0;i<n;i++){for(j=sumv;j>=v[i];j–){dp[j]=min(dp[j],dp[j-v[i]]+w[i]);}}for(j=sumv;j>=0;j–){if(dp[j]<=W){printf("%d\n",j);break;}}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
可你仍然感谢天地和人世所带来的这些变化和发生。
