0-1背包问题分析

for i in range(1, N+1):
    for j in range(1, W+1):
        ... ...

class Solution:
    def package(self, N, W, weights, values):
        # 创建数组并初始化
        dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
        # 遍历物品
        for i in range(1, N+1):
            # 当前物品重量
            pi = values[i-1]
            # 当前物品价值
            wi = weights[i-1]
            # 遍历背包
            for j in range(1, W+1):
                # 放不下的情况
                if wi > j:
                    # 沿用前面的价值
                    dp[i][j] = dp[i-1][j]
                # 放得下的情况
                else:
                    # 取"放"和"不放"两者的较大值
                    dp[i][j] = max(dp[i-1][j], pi+dp[i-1][j-wi])
        for i in dp: print(i)
        # 输出结果
        print(dp[-1][-1])

[0, 0, 0, 0, 0]
[0, 0, 4, 4, 4]
[0, 2, 4, 6, 6]
[0, 2, 4, 6, 6]
6