html5网站开发技术,小蜜蜂wordpress采集,优化推广网站推荐,seo搜索引擎优化兴盛优选题干#xff1a;
又见01背包
时间限制#xff1a;1000 ms | 内存限制#xff1a;65535 KB
难度#xff1a;3
输入
多组测试数据。 每组测试数据第一行输入#xff0c;n 和 W #xff0c;接下来有n行#xff0c;每行输入两个数#xff0c;代表第i个物品的wi 和 v…题干
又见01背包
时间限制1000 ms | 内存限制65535 KB
难度3
输入
多组测试数据。 每组测试数据第一行输入n 和 W 接下来有n行每行输入两个数代表第i个物品的wi 和 vi。
输出
满足题意的最大价值每组测试数据占一行。
样例输入
4 5
2 3
1 2
3 4
2 2
样例输出
7
来源
飘谊系列
上传者
TC_张友谊
描述 有n个重量和价值分别为wi 和 vi 的 物品从这些物品中选择总重量不超过 W
的物品求所有挑选方案中物品价值总和的最大值。 1 n 100 1 wi 10^7 1 vi 100 1 W 10^9
解题报告 因为这题w的数据量很大显然开不下这么大的空间但是反过来想这题可以认为是在相同价值中更新所需背包容量最小的那一种所以这题记录一下最大的价值v然后以v为数组下标跑0-1背包就可以了。注意初始化问题哦需要初始化成INF。 还有一道题跟这题很像【 FZU - 2214 】Knapsack problem
AC代码
#includebits/stdc.husing namespace std;
const int INF 0x3f3f3f3f;
int w[105],v[105];
int dp[10000 5];
int n,m;
int main()
{while(cinnm) {int sum 0;for(int i 1; in; i) {cinw[i]v[i];sum v[i];}memset(dp,INF,sizeof(dp));dp[0] 0;for(int i 1; in; i) {for(int j sum; jv[i]; j--) {dp[j] min(dp[j],dp[j - v[i]] w[i]) ;}}int ans 0;for(int i sum; i0; i--) {if(dp[i] m) {ans i;break;} }cout ans endl;}return 0 ;}
