打印背包中的麻袋

Question

假设你是一个小偷,你入侵了一所房子.你在里面找到了以下物品:

一个重3磅的花瓶,价值50美元.
一块重6磅的银块,价值30美元.
一幅重4磅,价值40美元的画作.
重量为5磅,价值10美元的镜子.

这个尺寸为10磅的背包问题的解决方案是90美元.

由动态编程制成的表格是: -

现在我想知道我使用这张表放入麻袋的哪些元素然后如何回溯？

Answer 1

从您的DP表我们知道f [i] [w] =总重量小于或等于w的项目1..i的子集的最大总值.

我们可以使用表本身来恢复最佳包装:

def reconstruct(i, w):  # reconstruct subset of items 1..i with weight <= w
                        # and value f[i][w]
  if i == 0: 
      # base case
      return {}
  if f[i][w] > f[i-1][w]:
      # we have to take item i
      return {i} UNION reconstruct(i-1, w - weight_of_item(i))
  else:
      # we don't need item i
      return reconstruct(i-1, w)