我正在尝试设计一个 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
的输出是一个布尔值。 - amit