背包问题的重复算法

Question

我正在尝试设计一个 Knapsack 算法的伪代码，其中单个物品可以被多次选中。经典算法为

OPT(i, w) = max(OPT(i-1, w) or vi + OPT(i-1, w-wi))

为了满足要求，我正在对其进行修改。

k=1;
max = maximum(OPT(i-1, w))
while(OPT(i-1, w - k*wi) > 0) {
  maximum = max(maximum, k*vi + OPT(i-1, w - k*wi))
  k++
}
OPT(i, w) = maximum

这个方案是否合适？还有更好的解决方案吗？如果需要任何额外信息，请告知。其余部分保持不变，vi表示第i个元素的值，wi表示第i个元素的重量。

- LearningToCode

Answer 1

如果您想选择多个项目，只需在选择元素时更改递归即可：

OPT(i, w) = max(OPT(i-1, w) or vi + OPT(i, w-wi))
                     ^                   ^
          removed the element      not removing the element

这个想法是，你在下一次迭代中允许重新读取它。你可以添加任意数量的元素，并在“选择”使用停止递归公式中的第一个条件时停止添加。

递归仍然不会无限制进行，因为你必须在 w<0 时停止。

时间复杂度不变 - O(nW)

- amit

---

有没有可能将这个问题简化为一个一维输出的问题？ - LearningToCode

我不明白你所说的“1D输出”是什么意思。OPT的输出是一个布尔值。 - amit

由于我们正在使用i和W作为变量，因此代码的空间复杂度为O(nW)。我们能否以某种方式将其减少到O(n)？ - LearningToCode

@LearningToCode 空间复杂度可以是O(W)，因为在每个点上，你只需要当前列和前一列的信息 - 从不超过这些，所以可以在O(W)的空间内完成，时间复杂度为O(nW)。 - amit

Answer 2

基于DVP算法，重复背包问题的解决方案如下：

K(0)=0
for w=1 to W:
    K(w) = max{K(w - w_i) + v_i, w_i < w}
return K(W)

这里，W是背包的容量；w_i是物品i的重量；v_i是物品i的价值；K(w)是在容量为w的背包中可达到的最大价值。

你的解决方案似乎是0-1背包问题。

- MoeChen