我正在尝试为 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个元素的权重。
最佳答案
如果你希望能够选择多个项目，你所要做的就是改变选择元素时的递归:
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)
关于重复背包算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33323300/