离散背包动态规划 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]的值所替换。有点尴尬的是，我已经为此工作了将近一个星期，还是无法弄清楚。除了课堂讲座视频之外，这个视频一直是我的主要参考资料。动态规划证明是一个相当大的挑战。

- cc77

---

可以多次选择同一块金条吗？ - akashchandrakar

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]

- cc77