nyoj860 又见01背包(背包变形）

nyoj860 又见01背包(背包变形）

题目860​​题目信息​​​​运行结果​​​​本题排行​​​​讨论区​​

又见01背包

1000 ms  |  内存限制： 65535

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 5 2 3 1 2 3 4 2 2

样例输出

7

如果用以前的背包做这道题，我们会发现质量的范围太大了 无法开数组。所以就会想到了转换。

这道题就是求最少的质量能装最大的价值。而我们又发现背包的价值范围不大。就会想到了用价值保存质量。

#include #include #include using namespace std;int main(){ int n,w,wi[105],vi[105],dp[10005]; while(scanf("%d %d",&n,&w)!=EOF) { int sum=0; memset(dp,100,sizeof(dp)); dp[0]=0; for(int i=0;i=vi[i];j--) dp[j]=min(dp[j],dp[j-vi[i]]+wi[i]); } for(int j=sum;j>=0;j--) if(dp[j]<=w) { printf("%d\n",j); break; } } return 0;}/*5 1010 510 610 710 110 2*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。