Python的二维01背包

Python的二维01背包是一种常见的动态规划问题，用于解决在给定背包容量和一组物品重量、价值的情况下，如何选择物品放入背包，使得背包中物品的总价值最大化，同时要求背包中物品的总重量不超过背包容量。

具体的解题思路如下：
1. 创建一个二维数组dp，其中dp[i][j]表示在前i个物品中，背包容量为j时的最大价值。
2. 初始化dp数组的第一行和第一列为0，表示背包容量为0或物品数量为0时的最大价值都为0。
3. 遍历物品列表，对于每个物品i，遍历背包容量j从0到背包总容量：
- 如果当前物品i的重量大于背包容量j，则无法放入背包，最大价值为dp[i-1][j]。
- 否则，可以选择放入或不放入当前物品i。如果选择放入，则最大价值为当前物品i的价值加上dp[i-1][j-当前物品i的重量]；如果选择不放入，则最大价值为dp[i-1][j]。取两者中的较大值作为dp[i][j]的值。
4. 遍历完所有物品后，dp[-1][-1]即为问题的最优解，即背包中物品的最大总价值。

下面是Python代码示例：

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

    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])

    return dp[-1][-1]