试图找出经典的背包再现

Question

我正在阅读Knapsack Problem(无界),正如我理解DP中的经典之作.
虽然我认为我在阅读时理解了解决方案,但我不清楚如何将其转换为实际代码.
例如,在以下重复"公式"中:

M(j) = MAX {M(j-1), MAX i = 1 to n (M(j - Si) + Vi) } for j >=1

我不知道如何将其转换为代码,因为我不清楚内部MAX应该在那里还是应该只是代替:
M(j) = MAX {M(j-1), M(j - Si) + Vi } for j >=1

有什么帮助找出公式并编码吗？

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的最佳子集,其总重量> w,或

2)具有总重量> w-wk加上项目k的Sk-1的最佳子集

具有总重量> w的Sk的最佳子集,或者包含项k或者不包含项k.

第一种情况:wk> w.项目k不能成为解决方案的一部分,因为如果是,则总重量将> w,这是不可接受的.

第二种情况:wk <= w.然后项目k可以在解决方案中,我们选择具有更大价值的案例.