动态规划解背包问题

题目

题解

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]