打印背包里麻袋里的物品 [英] Printing Items that are in sack in knapsack

问题描述

假设您是小偷，您入侵了一所房子.在里面发现了以下物品:

Suppose you are a thief and you invaded a house. Inside you found the following items:

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

A vase that weights 3 pounds and is worth 50 dollars.
A silver nugget that weights 6 pounds and is worth 30 dollars.
A painting that weights 4 pounds and is worth 40 dollars.
A mirror that weights 5 pounds and is worth 10 dollars.

这个10磅大小的背包问题的解决方案是90美元.

Solution to this Knapsack problem of size 10 pounds is 90 dollars .

通过动态编程制成的表是:-

Table made from dynamic programming is :-

现在，我想知道使用该表将哪些元素放入了麻袋，然后如何回溯?

推荐答案

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

From your DP table we know f[i][w] = the maximum total value of a subset of items 1..i that has total weight less than or equal to w.

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

We can use the table itself to restore the optimal packing:

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)

这篇关于打印背包里麻袋里的物品的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！