01背包问题 python代码

01背包问题是一个经典的动态规划问题。给定一组物品，每个物品有一个重量和一个价值，在限定的总重量内，如何选择物品使得总价值最大。

以下是一个Python实现的01背包问题的代码示例：

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

    for i in range(1, n + 1):
        for w in range(capacity + 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][capacity]

# 示例使用
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print("最大价值:", knapsack(weights, values, capacity))

在这个代码中，我们使用了二维动态规划数组`dp`，其中`dp[i][w]`表示前`i`个物品在容量为`w`的情况下的最大价值。通过遍历每个物品和每个可能的重量，更新`dp`数组，最终得到最大价值。