试图找出经典背包循环

Question

我正在阅读背包问题（无界），正如我所理解的DP中的经典。
虽然我认为我在阅读时理解了解决方案，但我不清楚如何将其翻译为实际代码。
例如在以下递归“公式”中：

<代码>M（j）=MAX{M（j-1）， MAX i=1 to n（M（j-Si）Vi）}for j

我不确定如何将其翻译成代码，因为我不清楚内部MAX应该在那里还是应该在那里：
M（j）=MAX{M（j-1）， M（j-Si）Vi}代表j




Answer 1

您可以这样编码：

for w = 0 to W   //W is the maximum capacity
V[0,w] = 0
for i = 1 to n
V[i,0] = 0
for i = 1 to n
for w = 0 to W
    if wi <= w // item i can be part of the solution
        if  bi + V[i-1,w-wi] > V[i-1,w]
            V[i,w] = bi + V[i-1,w- wi]
        else
            V[i,w] = V[i-1,w]
    else V[i,w] = V[i-1,w]  // wi > w 

这意味着以下内容：

这意味着，总权重w的Sk的最佳子集是：

1） 具有总权重的Sk-1的最佳子集

2）具有总权重的SK-1的最佳子集

具有总重量的Sk的最佳子集

第一种情况：wk

第二种情况：wk