python - 离散背包动态规划Python3

Question

这是我处理动态规划的第一份作业，我发现它相当困难。

问题:

给定一个容量为 W 的背包和 n 根重量为 [wt[0],...,wt[n - 1] 的金条，求不重复地装入背包的最大金条数。

输入: 第1行:(容量背包(W))(金条数(n)) 第2行:n根金条的重量(wt)

输出:容量为W的背包所能容纳的最大重量(金条)

我的代码:

import sys

def optimal_weight(W, wt):
    """Find max weight that can fit in knapsack size W."""
    # Create n nested arrays of 0 * (W + 1)
    max_vals = [[0] * (W + 1) for x in range(len(wt))]
    # Set max_vals[0] to wt[0] if wt[0] <= j
    max_vals[0] = [wt[0] if wt[0] <= j else 0 for j in range(W + 1)]
    for i in range(1, len(wt)):
        for j in range(1, W + 1):
            value = max_vals[i - 1][j]  # previous i @ same j
            if wt[i] <= j:
                val = (max_vals[i - 1][j - wt[i]]) + wt[i]
                if value < val:
                    value = val
                    max_vals[i][j] = value
                else:
                    max_vals[i][j] = value

    return max_vals[-1][-1]

if __name__ == '__main__':
    input = sys.stdin.read()
    W, n, *wt = list(map(int, input.split()))
    print(optimal_weight(W, wt))

有什么地方出错了吗？当我观察我的结尾 max_vals 时，我看到随着 i 的增加，max_vals 只会替换每个嵌套列表中越来越小的值 (i - 1)。换句话说，随着我继续迭代，越来越少的 0 被 max_vals[i - 1][j] 的值替换。有点尴尬，我已经为此工作了将近一个星期，但无法弄清楚。 This video ，除了类讲座视频，一直是我的主要引用点。动态规划被证明是一个相当大的挑战。

Answer 1

非常简单的修复。不敢相信我错过了。只是弄乱了 else 语句。需要额外的。

        if value < val:
                value = val
                max_vals[i][j] = value
            else:
                max_vals[i][j] = value  # set to [i - 1][j]
        else:
            max_vals[i][j] = value   # set to [i - 1][j]