反向0/1背包:表中的这一行是怎么可能的？

Question

我正在解决一个反向的0/1背包问题，也就是说，我试图仅使用DP表重新创建所有项目的权重和值列表。

我有一张桌子：

    [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

我不明白第二行怎么可能。

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

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

当我们达到2时，我们有6，6> 2-1，我假设这里使用两个项目，一个weight = 1和value = 4 (旧的)，weight = 4-1和value = 6-4 = weight = 3和value = 2，这是新的。

问题：怎么可能有2= 10？我们不能把超过一个项目排在一排，因为我理解这个图表。如果我们在这里使用两个项，那么对于第2行中的所有元素，从2开始到行尾，难道不应该有6吗？

Answer 1

这似乎是可能的，如果你有两个项目，一个有重量1和值4和一个与重量4，值6。

多么?当您在索引(2，4)时，在考虑项2(权重4，值6)的行中，您的权重容量为4。这允许您获取值为6的项，而不是以前在索引(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]?