在背包中打印袋子里的物品

Question

假设您是一名小偷，闯入了一所房子。你找到了以下物品：

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

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

使用动态规划的方法制作的表如下：

现在我想知道如何根据这个表格选择装进我的口袋中的物品，以及如何回溯？

- T.J.

Answer 1

从DP表中，我们可以得知f[i][w]表示物品1..i的子集中总重量小于等于w时的最大总价值。

我们可以使用这个表本身来恢复最优的打包方案：

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)

- Niklas B.

---

嘿，你能给我一些内部想法，让我更好地了解这个算法吗？ - T.J.

@T.J 如果您想要更清楚地了解，您需要提供更具体的信息。递归的工作原理如下：如果 f[i][w] <= f[i-1][w]，那么我们不需要物品 i，所以我们只需递归到子集 1..i-1。如果 f[i][w] > f[i-1][w]，那么我们需要使用物品 i 来达到最优结果，因此我们将其放入背包中。剩余的背包容量为 w-weight of item i，我们希望尽可能多地将物品 1..i-1 装入该剩余容量中。 - Niklas B.

我认为这个想法也可以表述如下。在动态规划的末尾，选择一个最优状态以获得最优值。回溯用于找出“前一个”状态，即生成最优状态的基础状态。然后，在此前一个状态上迭代回溯，直到找到初始状态（即空背包）。我认为这很有见地，因为我曾经相信多年必须维护一些辅助结构来引用状态空间中相应的前一个状态。 - Codor

@Codor 嗯，确实需要存储额外的信息。为了仅获取最优值，您只需要读取 DP 数组中连续的两行即可。 - Niklas B.

@NiklasB。非常好的观点；对于计算最优值，只需要同时表示整个状态空间中的最优值，而不是整个状态空间。 - Codor

Answer 2

我有一个迭代算法，受@NiklasB的启发。当递归算法达到某种递归限制时，该算法可以发挥作用。

def reconstruct(i, w, kp_soln, weight_of_item):
    """
    Reconstruct subset of items i with weights w. The two inputs
    i and w are taken at the point of optimality in the knapsack soln

    In this case I just assume that i is some number from a range
    0,1,2,...n
    """
    recon = set()
    # assuming our kp soln converged, we stopped at the ith item, so
    # start here and work our way backwards through all the items in
    # the list of kp solns. If an item was deemed optimal by kp, then
    # put it in our bag, otherwise skip it.
    for j in range(0, i+1)[::-1]:
        cur_val = kp_soln[j][w]
        prev_val = kp_soln[j-1][w]
        if cur_val > prev_val:
            recon.add(j)
            w = w - weight_of_item[j]
    return recon

- Greg

Answer 3

使用循环：

   for (int n = N, w = W; n > 0; n--)
            {
                if (sol[n][w] != 0)
                {
                    selected[n] = 1;
                    w = w - wt[n];
                }
                else
                    selected[n] = 0;
            }
            System.out.print("\nItems with weight ");
            for (int i = 1; i < N + 1; i++)
                if (selected[i] == 1)
                    System.out.print(val[i] +" ");

- Divyanshu Jimmy