2

我正在阅读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

任何帮助找出公式并对其进行编码？

4

1 回答 1

7

你可以这样编码：

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) 总权重 > w 的 Sk-1 的最佳子集，或

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

总权重 > w 的 Sk 的最佳子集，要么包含项目 k，要么不包含项目 k。

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

第二种情况：wk <= w。那么项目 k 可以在解中，我们选择价值更大的情况。

于 2012-12-31T16:28:59.830 回答