背包重复算法

Question

我正在尝试为背包算法设计一个伪代码，其中可以多次选择单个项目。经典算法是

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个元素的权重。

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)