重复背包算法

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

Answer 1

如果你希望能够选择多个项目，你所要做的就是改变选择元素时的递归：

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

想法是，您允许在下一次迭代时读取它。一个元素你想加多少就加多少，当你"chose"使用停止递归公式中的第一个条件时你停止添加。

递归仍然不会是无限的，因为你必须停止一次w<0。

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

Answer 2

基于Algorithms DVP，Knapsack with repetition的解法如下：

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 Knapsack。

重复背包算法

Algorithm for Knapsack with repetition

algorithm

pseudocode

knapsack-problem

dynamic-programming