0-1背包重温
0-1背包重温
提问于 2012-06-07 16:42:15
好吧，这是一个古老的0-1背包问题，但在找到我能得到的总最高价格后，我需要找到我能携带的物品。但是对于下面的测试用例(总共3个项目)
10 (max weight that I can carry)
5 3 (weight and value for each item)
5 2
6 5这里的最高价格是5，但重量可以是6或10(5+5)。两者都会给出相同的价格，但显然可行的是拿6公斤的东西而不是10公斤的东西。我想要一个提示，我如何从dp矩阵中计算出来。我得到了这个测试用例的以下矩阵。
0 0 0 0 3 3 3 3 3 3
0 0 0 0 3 3 3 3 3 5
0 0 0 0 3 5 5 5 5 5 使用这个算法，它发现重量是10，但最优的是6公斤。
i=n, k=W(max weight)// n= total items
while i,k > 0
if dp[i,k] ≠ dp[i−1,k] then
mark the ith item as in the knapsack
i = i−1, k = k-w(weight of ith item)
else
i = i−1回答 1
Stack Overflow用户
发布于 2012-06-07 16:59:28
简单的解决方案是在不同的袋子大小上迭代运行背包算法，并选择最小的袋子，它仍然给你提供与原始袋子相同的值。
这可以在重量[0,W]上使用binary search来完成-所以你将运行背包算法总的O(logW)次，给你总的O(nW*log(W))解，找到最大值和最小可能的袋子大小。
关于如何实现二进制搜索的想法：
让原始包的大小为W，运行knapsack(W,items)并获取value。现在检查knapsack(W/2,items)是否仍然返回value。如果是这样的话-在range (0,W/2]中搜索。如果没有，请在range (W/2,W]中搜索，直到找到返回value的最小袋子尺寸。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/10928477
复制相关文章
相似问题
腾讯云开发者
