题目

题解

def knapsac(W: int, N: int, wt: List[int], val: List[int]) -> int:
    # 定义状态动作价值函数: dp[i][j]，对于前i个物品，当前背包容量为j，最大的可装载价值
    dp = [[0 for j in range(W+1)] for i in range(N+1)]

    # 状态动作转移
    for i in range(1, N+1):
        for w in range(1, W+1):
            # 边界条件判断：当当前容量足以容纳第i个商品时，有两种选择
            if w - wt[i-1] > 0:
             	# # 放入第i个物品 vs 不放入
                dp[i][w] = max(dp[i-1][w - wt[i-1]] + val[i-1], dp[i-1][w])
            # 否则只有1种选择，不放
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[N][W]