动态规划求01背包问题python

### 使用Python通过动态规划解决01背包问题

#### 解决方案概述
为了有效解决01背包问题，可以利用动态规划的思想。此方法的核心在于构建一个二维数组`dp`，其中`dp[i][j]`代表前i个物品放入容量为j的背包可以获得的最大价值[^2]。

#### 动态转移方程
对于每一个物品有两种情况：不放入当前考虑的第i个物品；或者放入第i个物品。具体来说：

- 如果不放，则最大价值等于之前已经计算过的`dp[i-1][j]`
- 如果放，则要看剩余空间能否容纳这个新加入的物品以及其带来的额外价值`value[i]+dp[i-1][j-weight[i]]`

最终取两者之间的较大者作为新的`dp[i][j]`值[^3]。

def knapsack_01(weights, values, capacity):
    n = len(values)
    
    # 创建并初始化dp表
    dp = [[0]*(capacity+1) for _ in range(n+1)]
    
    # 填充dp表格
    for i in range(1, n+1):  # 物品编号从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]

这段代码实现了上述逻辑，输入参数分别为各个项目的重量列表、价值列表以及背包总承重能力。返回的结果是所能获得的最大总价值。