背包查找最大值

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) if weight[i] <= w
dp[i][w] = dp[i-1][w] if weight[i] > w

dp[0][w] = 0 for all w
dp[i][0] = 0 for all i

dp[i][w] = max(dp[i-1][w], dp[i][w-weight[i]] + value[i]) if weight[i] <= w
dp[i][w] = dp[i-1][w] if weight[i] > w

dp[0][w] = 0 for all w
dp[i][0] = 0 for all i

def knapsack_01(weights, values, max_weight):
    n = len(weights)
    dp = [[0] * (max_weight + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, max_weight + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][max_weight]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
max_weight = 5
print(knapsack_01(weights, values, max_weight))  # 输出：7