0/1 背包问题的混淆输出

Question

我正在学习动态规划，并且有书Grokking Algorithms

那里给出的示例使用这些 images/values:

当我运行下面的代码，它应该在 Python 中实现 0/1 背包问题时，我得到以下输出：

+---+------+------+------+------+
| 0 |  0   |  0   |  0   |  0   |
| 0 | 1500 | 1500 | 1500 | 1500 |
| 0 | 1500 | 1500 | 2000 | 3500 |
| 0 | 1500 | 1500 | 2000 | 3500 |
+---+------+------+------+------+
3500

答案是正确的，但看起来这是巧合，因为代码生成的table与书中图片给出的不同。

谁能解释一下为什么代码生成的table和书上的不一样？

会不会是用于生成 table 的公式不同（实际上不同 - 我可以看出它们不相同）？书上的是：

# A Dynamic Programming based Python
# Program for 0-1 Knapsack problem
# Returns the maximum value that can
# be put in a knapsack of capacity W
from tabulate import tabulate


def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    # Build table K[][] in bottom up manner
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1]
                              + K[i - 1][w - wt[i - 1]],
                              K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]
    print(tabulate(K, tablefmt="pretty"))

    return K[n][W]


# Driver code
val = [1500, 2000, 3000]
wt = [1, 3, 4]
W = 4
n = len(val)
print(knapSack(W, wt, val, n))

Answer 1

+---+------+------+------+------+
| 0 |  0   |  0   |  0   |  0   |
| 0 | 1500 | 1500 | 1500 | 1500 |  guitar
| 0 | 1500 | 1500 | 2000 | 3500 |  laptop
| 0 | 1500 | 1500 | 2000 | 3500 |  stereo
+---+------+------+------+------+
3500

你的listing是[guitar, laptop, stereo]，但是在作者的解决方案中，listing是[guitar, stereo, laptop]。这就是为什么您的桌子不同的原因，仅此而已。您的解决方案确实是正确的。尝试运行您的解决方案与作者列表：

from tabulate import tabulate

def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    # Build table K[][] in bottom up manner
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1]
                              + K[i - 1][w - wt[i - 1]],
                              K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]
    print(tabulate(K, tablefmt="pretty"))

    return K[n][W]


# Driver code
val = [1500, 3000, 2000]
wt = [1, 4, 3]
W = 4
n = len(val)
print(knapSack(W, wt, val, n))

输出：

+---+------+------+------+------+
| 0 |  0   |  0   |  0   |  0   |
| 0 | 1500 | 1500 | 1500 | 1500 |   guitar
| 0 | 1500 | 1500 | 1500 | 3000 |   stereo
| 0 | 1500 | 1500 | 2000 | 3500 |   laptop
+---+------+------+------+------+
3500

0/1 背包问题的混淆输出

Confusing Output for 0/1 Knapsack Problem

python

algorithm

dynamic-programming