二维0-1背包问题 动态规划思路 python代码实现

二维0-1背包问题是一个经典的动态规划问题，它涉及到物品的重量和价值，以及一个有限容量的背包。每个物品都有一个重量和一个价值，目标是在不超过背包总容量的前提下，选择能够获得最大价值的一组物品。

动态规划的思路通常是这样的：
1. 初始化一个二维数组，其中`dp[i][j]`表示前i个物品的最大价值，当背包容量为j时。
2. 从第一个物品开始遍历，对于每个物品，有两种选择：装入背包或不装入。如果装入，那么新的状态就是当前物品的价值加上之前剩余容量下的最大价值；如果不装入，就保持之前的值不变。
3. 更新所有可能的状态，直到处理完所有的物品和所有可能的背包容量。
4. 最终`dp[n][W]`就是最大的价值，n为物品总数，W为背包容量。

以下是Python代码的一个简单实现：

def knapsack_2d(dp, weights, values, capacity):
    n, m = len(weights), len(values)
    for i in range(1, n + 1):
        for j in range(capacity + 1):
            if j < weights[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
    return dp[n][capacity]

weights = [5, 6, 7]
values = [10, 15, 20]
capacity = 11
dp = [[0] * (capacity + 1) for _ in range(len(weights) + 1)]
max_value = knapsack_2d(dp, weights, values, capacity)

print(f"最大价值为: {max_value}")