algorithm - 0-1 背包重访

Question

好吧，这是一个古老的 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

Answer 1

简单的解决方案是在不同的袋子尺寸上迭代地运行背包算法，并选择最小的袋子，它仍然可以为您提供与原始袋子相同的价值。

这可以使用对重量的二分搜索[0,W]来完成- 因此您将运行背包算法的总O(logW)次数，为您提供O(nW*log(W))找到最大值和可能的最小袋子大小的总解决方案。

如何隐含二分搜索的想法：
让原始包的大小为W，运行knapsack(W,items)，得到value. 现在检查是否knapsack(W/2,items)仍然返回value。如果是 - 在范围内搜索(0,W/2]。如果没有，请在 range 中搜索(W/2,W]，直到找到返回的最小袋子尺寸value。