用python写01背包问题的代码

以下是 Python 实现 01 背包问题的代码：

def knapsack01(W, wt, val, n):
    """
    W: 背包容量
    wt: 物品重量列表
    val: 物品价值列表
    n: 物品数量
    """
    # 使用二维数组 dp[i][j] 记录前 i 个物品中，容量为 j 的背包所能获得的最大价值
    dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
    
    # 递推计算 dp 数组
    for i in range(1, n+1):
        for j in range(1, W+1):
            if j < wt[i-1]:  # 当前背包容量不足以放下物品 i
                dp[i][j] = dp[i-1][j]
            else:  # 当前背包容量可以放下物品 i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1])
    
    # 返回最大价值
    return dp[n][W]

# 示例
W = 10
wt = [2, 3, 4, 5]
val = [3, 4, 5, 6]
n = len(wt)
print(knapsack01(W, wt, val, n))  # 输出 10

在上述代码中，我们使用二维数组 `dp` 来记录前 `i` 个物品中，容量为 `j` 的背包所能获得的最大价值。具体来说，`dp[i][j]` 表示前 `i` 个物品中，容量为 `j` 的背包所能获得的最大价值。

接着，我们使用两个循环来递推计算 `dp` 数组。在循环中，我们通过比较将当前物品放入背包和不放入背包两种情况的价值，来确定背包的最大价值。

最后，我们返回 `dp[n][W]`，即前 `n` 个物品中，容量为 `W` 的背包所能获得的最大价值。