时间戳

首页 > 解决方案 > 反向 0/1 背包：表中的这一行怎么可能？

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

问题描述

我正在解决反向 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

我不明白如何行 [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][4] 到行尾的第 [2] 行中的所有元素不应该有 6 个吗？

标签： algorithmdynamic-programmingknapsack-problem

解决方案

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

如何？当您处于索引 (2, 4) 时，您在考虑项目 2 的行中的重量容量首次为 4（重量 4，值 6）。这使您可以获取值为 6 的项目，而不是之前在索引 (2, 3) 获取的权重为 1、值 4 的项目，有效地从索引 (2, 0) 处的子问题构建。

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

另请参阅如何使用背包算法查找包中的哪些元素[而不仅仅是包的价值]？

推荐阅读