algorithm - 打印背包中袋子里的元素

Question

假设你是一个小偷，你闯入了一所房子。您在里面找到了以下元素:

一个重3磅、值(value)50美元的花瓶。
一 block 重 6 磅、值(value) 30 美元的银 block 。
一幅重4磅、值(value)40美元的画。
一面重 5 磅、值(value) 10 美元的镜子。

这个 10 磅背包问题的解是 90 美元。

由动态规划制成的表是:-

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

Answer 1

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

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

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)