反向 0/1 背包：table 中的这一行怎么可能？

Question

我正在解决反向 0/1 背包问题，即我正在尝试仅使用 DP-table.

重新创建所有项目的重量和价值列表

我有这个table:

    [0][1]   [4][5][6]               [12]
[0]  0  0 0 0 0  0  0  0  0  0  0  0  0
[1]  0  4 4 4 4  4  4  4  4  4  4  4  4  
[2]  0  4 4 4 6 10 10 10 10 10 10 10 10

我不明白第 [2] 行怎么可能。

[0] - 很明显，如果我们不在背包里放任何东西，答案总值为0.

[1] - 在行 [1] 中，我看到 [1][1]=4，我希望我正确地得出第一个项目有 weight = 1 和 value = 4 的结论。所以，因为我们只放了 1 件物品，所以它是我们希望在这一行中唯一的重量。

[2] - 当我们到达 [2][4] 时，我们有 6、6 > [2-1][4] 我假设我们在这里使用 2 个项目，一个 weight = 1 和value = 4（旧的）和weight = 4-1和value = 6-4 = weight = 3和value = 2，这是新的

问题: [2][5] = 10 怎么可能？根据我对这张图表的理解，我们不能连续放置超过 1 个项目。如果我们在这里使用了两个项目，我们不应该为第 [2] 行中从 [2][4] 到行末的所有元素设置 6 个吗？

Answer 1

如果您有两件物品，一件重量为 1，价值 4，另一件重量为 4，价值 6，这似乎是可能的。

怎么样？当您位于索引 (2, 4) 时，您在考虑项目 2 的行中第一次具有 4 的承重能力（重量 4，值 6）。这使您可以取值为 6 的项目而不是 的权重 1，您之前在索引 (2, 3) 处取的值为 4 的项目，有效地从索引 (2, 0) 处的子问题构建).

现在，当您位于索引 (2, 5) 且承重量为 5 时，总值为 10 是可能的，因为您可以同时拿走这两项。这是您可以为该行的其余部分做的最好的事情。

另见 How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?

反向 0/1 背包：table 中的这一行怎么可能？

Reverse 0/1 knapsack: how is this row in the table possible?

algorithm

knapsack-problem

dynamic-programming