从背包中检索项[一维数组实现]
从背包中检索项[一维数组实现]
提问于 2014-03-07 09:37:51
这个算法在Are these 2 knapsack algorithms the same? (Do they always output the same thing)上运行良好。
我们如何检索流程中选择的项目？
这是上一篇文章中的算法
for (int j = 0; j < N; j++) {
if (C-w[j] < 0) continue;
for (int i = C-w[j]; i >= 0; --i) { //loop backwards to prevent double counting
dp[i + w[j]] = max(dp[i + w[j]], dp[i] + v[j]); //looping fwd is for the unbounded problem
}
}
printf( "max value without double counting (loop backwards) %d\n", dp[C]);这是一个示例：
For C = 9 and N = 3
Values and Weights:
5 4
6 5
3 2背包数组如下：
0 0 3 3 5 6 8 9 9 11 它通过选择项目1和项目2给出了最佳值= 11
如何检索所选项目？或者如何知道我们选择了哪些项目？项目1和项目2
添加另一个示例：
weight: 16 19 23 28
value: 2 3 4 5
C = 7迭代1
0 16 16 16 16 16 16迭代2
0 16 19 19 35 35 35迭代3
0 16 19 23 35 39 42迭代4
0 16 19 28 35 39 44对于第1项和第4项，最佳值= 44
回答 1
Stack Overflow用户
发布于 2014-03-07 14:32:01
只需通过检查刚找到的解决方案是否比之前看到的任何解决方案更好来替换您的最大调用。如果是这样的话，就把它保存起来，以便以后参考。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22239802
复制相关文章
相似问题
腾讯云开发者
