好吧，这是一个古老的 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
最佳答案
简单的解决方案是在不同尺寸的袋子上迭代运行背包算法，并选择最小的袋子，它仍然为您提供与原始袋子相同的值(value)。
这可以使用 binary search 来完成在权重上 [0,W] - 所以你将运行背包算法总共 O(logW) 次，给你总共 O(nW*log (W)) 找到最大值和最小可能包大小的解决方案。
如何隐含二分查找的想法:
设原始包的大小为W，运行knapsack(W,items)，得到值。现在检查 knapsack(W/2,items) 是否仍然返回 value。如果是 - 在 (0,W/2] 范围内搜索。如果不是，则在 (W/2,W] 范围内搜索，直到找到返回 value 的最小包大小。
关于algorithm - 0-1 背包重访，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10928477/