二维背包问题动态规划详解（二维01背包）

## 二维背包问题动态规划详解### 简介二维背包问题是动态规划中的一种经典问题，它与经典的背包问题类似，但增加了一个额外的维度（通常称为容量）。在这个问题中，除了物品的重量之外，还需要考虑物品的另一个属性（例如体积或价值），并且背包有两个容量限制（例如重量和体积）。### 问题描述给定一个背包，其容量分别为 `W1` 和 `W2`，以及 `n` 件物品，每件物品具有重量 `w1[i]` 和 `w2[i]`，以及价值 `v[i]`。目标是找到一个物品子集，使得其总重量不超过 `W1` 和 `W2`，且总价值最大。### 动态规划解决方案二维背包问题的动态规划解决方案使用一个二维表格 `dp`，其中 `dp[i][j]` 表示考虑前 `i` 件物品时，在容量限制 `(j1, j2)` 下的最大价值。

初始化：

``` dp[0][0] = 0 # 当没有物品或容量时，价值为 0 ```

状态转移方程：

对于第 `i` 件物品：

不选第 `i` 件物品：

``` dp[i][j1][j2] = dp[i-1][j1][j2] ```

选第 `i` 件物品，且不超过容量限制：

``` dp[i][j1][j2] = max(dp[i-1][j1][j2], dp[i-1][j1 - w1[i]][j2 - w2[i]] + v[i]) ```

注意：

如果物品 `i` 的重量/体积超过了容量限制，则不能选择。### 时间复杂度二维背包问题的动态规划解决方案的时间复杂度为 `O(n

W1

W2)`，其中 `n` 为物品数量，`W1` 和 `W2` 为背包容量。### 示例给定背包容量 `W1 = 10` 和 `W2 = 5`，以及物品信息如下：| 物品 | w1 | w2 | v | |---|---|---|---| | A | 3 | 2 | 4 | | B | 4 | 3 | 6 | | C | 5 | 1 | 2 |

动态规划表格：

```| 0 1 2 3 4 5 6 7 8 9 10j1\j2 | 0 0 0 0 0 0 0 0 0 0 0 |j1 | -|---|---|---|---|---|---|---|---|---|---|0 | 0 0 0 0 0 0 0 0 0 0 0 0 |-|---|---|---|---|---|---|---|---|---|---|---|---|1 | 0 0 0 0 0 0 0 0 0 0 0 0 |-|---|---|---|---|---|---|---|---|---|---|---|---|2 | 0 0 0 0 0 0 0 0 0 0 0 0 |-|---|---|---|---|---|---|---|---|---|---|---|---|3 | 0 0 0 4 4 4 4 4 4 4 4 4 |-|---|---|---|---|---|---|---|---|---|---|---|---|4 | 0 0 0 4 6 6 6 6 6 6 6 6 |-|---|---|---|---|---|---|---|---|---|---|---|---|5 | 0 0 0 4 6 6 6 6 8 8 8 8 | ```

最优解：

选择物品 A 和 B，总重量为 7（不超过容量限制），总价值为 10。### 扩展和应用二维背包问题可以扩展到更多维度，例如三维或四维背包问题。它广泛应用于各种实际问题中，例如资源分配、装箱问题和库存优化。

二维背包问题动态规划详解

简介二维背包问题是动态规划中的一种经典问题，它与经典的背包问题类似，但增加了一个额外的维度（通常称为容量）。在这个问题中，除了物品的重量之外，还需要考虑物品的另一个属性（例如体积或价值），并且背包有两个容量限制（例如重量和体积）。

问题描述给定一个背包，其容量分别为 `W1` 和 `W2`，以及 `n` 件物品，每件物品具有重量 `w1[i]` 和 `w2[i]`，以及价值 `v[i]`。目标是找到一个物品子集，使得其总重量不超过 `W1` 和 `W2`，且总价值最大。

动态规划解决方案二维背包问题的动态规划解决方案使用一个二维表格 `dp`，其中 `dp[i][j]` 表示考虑前 `i` 件物品时，在容量限制 `(j1, j2)` 下的最大价值。**初始化：** ``` dp[0][0] = 0

当没有物品或容量时，价值为 0 ```**状态转移方程：**对于第 `i` 件物品：* **不选第 `i` 件物品：** ``` dp[i][j1][j2] = dp[i-1][j1][j2] ```* **选第 `i` 件物品，且不超过容量限制：** ``` dp[i][j1][j2] = max(dp[i-1][j1][j2], dp[i-1][j1 - w1[i]][j2 - w2[i]] + v[i]) ```**注意：**如果物品 `i` 的重量/体积超过了容量限制，则不能选择。

时间复杂度二维背包问题的动态规划解决方案的时间复杂度为 `O(n * W1 * W2)`，其中 `n` 为物品数量，`W1` 和 `W2` 为背包容量。

示例给定背包容量 `W1 = 10` 和 `W2 = 5`，以及物品信息如下：| 物品 | w1 | w2 | v | |---|---|---|---| | A | 3 | 2 | 4 | | B | 4 | 3 | 6 | | C | 5 | 1 | 2 |**动态规划表格：**```| 0 1 2 3 4 5 6 7 8 9 10j1\j2 | 0 0 0 0 0 0 0 0 0 0 0 |j1 | -|---|---|---|---|---|---|---|---|---|---|0 | 0 0 0 0 0 0 0 0 0 0 0 0 |-|---|---|---|---|---|---|---|---|---|---|---|---|1 | 0 0 0 0 0 0 0 0 0 0 0 0 |-|---|---|---|---|---|---|---|---|---|---|---|---|2 | 0 0 0 0 0 0 0 0 0 0 0 0 |-|---|---|---|---|---|---|---|---|---|---|---|---|3 | 0 0 0 4 4 4 4 4 4 4 4 4 |-|---|---|---|---|---|---|---|---|---|---|---|---|4 | 0 0 0 4 6 6 6 6 6 6 6 6 |-|---|---|---|---|---|---|---|---|---|---|---|---|5 | 0 0 0 4 6 6 6 6 8 8 8 8 | ```**最优解：**选择物品 A 和 B，总重量为 7（不超过容量限制），总价值为 10。

扩展和应用二维背包问题可以扩展到更多维度，例如三维或四维背包问题。它广泛应用于各种实际问题中，例如资源分配、装箱问题和库存优化。