> For the complete documentation index, see [llms.txt](https://anjia1.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://anjia1.gitbook.io/ds-algo/algo/dp/bag.md).

# 4.2.5 动态规划之背包问题

## 0/1 背包

给定 N 个物品，其中第 i 个物品的体积是 Vi，价值是 Wi。有一个容积为 M 的背包，要求选择一些物品放入背包，使得在总体积不超过 M 的前提下，物品的价值总和最大。

### 朴素思路

依次考虑每个物品选还是不选——即子集问题，每个结点有 2 个分支，是个 2^n 指数级别的搜索。同时关注已经放入背包里的物品的总重量和总价值。“子集问题”详见[《递归》](/ds-algo/non-linear/sub-problems/recursion.md)部分。

### 动态规划

1. 重复子问题：`opt[i][j]` 表示从前 i 个物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和
   * 状态：物品 `[i]` 和总体积 `[j]`
   * 最优化目标：`opt[i][j]` 最大价值总和
2. 决策：对于第 i 个物品，可以做的决策是选或者不选
   * 当不选时，`opt[i][j] = opt[i-1][j]`
   * 当选择时，`opt[i][j] = opt[i-1][j-Vi] + Wi`
   * 而 `opt[i][j]` 的值就取以上两个中值最大的那个
     * 递推公式：`opt[i][j] = max(opt[i-1][j], opt[i-1][j-Vi] + Wi)`
3. 开始递推
   * 默认值：`opt[i][j] = -Infinity`
   * 起点：`opt[0][0] = 0`
   * 目标：`max(...opt[N])`

动态规划的核心代码：

```javascript
// 最优化目标：opt[i][j] 表示从前 i 个物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和
let opt = new Array(N + 1); // (N+1)*(M+1)，多申请一个-当保护结点-以方便递推
for (let i = 0; i <= N; i++) opt[i] = new Array(M + 1).fill(-Infinity);
opt[0][0] = 0; // 递归起点

// 从小到大开始递推，先 for 状态，再 for 决策
for (let i = 1; i <= N; i++) { // [i] 物品
  for (let j = 0; j <= M; j++) { // [j] 总体积
    // 决策：选or不选
    opt[i][j] = opt[i - 1][j]; // 不选
    if (j >= V[i]) {
      opt[i][j] = Math.max(opt[i][j], opt[i - 1][j - V[i]] + W[i]); // 选
    }
  }
}

return Math.max(...opt[N]);
```

我们发现，状态 `opt[i]` 是先从 `opt[i-1]` 完全转移过来（当不选第 i 个物品时），然后是当 `j >= V[i]` 时，走“选择第 i 个物品”的决策。所以，在空间上，我们可以省略掉第一维的物品 `[i]` ，只留总体积 `[j]` 的维度。优化后的代码，如下：

```javascript
// 最优化目标：opt[i][j] 表示从前 i 个物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和
let opt = new Array(M + 1).fill(-Infinity); // 省略了第一维，从 (N+1)*(M+1) 降低为 (M+1)
opt[0] = 0; // 递推起点

// 从小到大开始递推，先 for 状态，再 for 决策
for (let i = 1; i <= N; i++) { // [i] 物品
  // for (let j = V[i]; j <= M; j++) { // [j] 总体积
  for (let j = M; j >= V[i]; j--) { // 须倒序遍历 [j]，才能拿到之前二维时纯粹的 opt[i-1][j]
    opt[j] = Math.max(opt[j], opt[j - V[i]] + W[i]); // max(不选, 选)
  }
}

return Math.max(...opt);
```

代码的空间复杂度从 O(N\*M) 降到了 O(M)。这就是 0/1 背包算法的通用代码，背包问题是一类特殊的动态规划问题。

看个例子感受下。

### 例 1：分割等和子集

> 题目：[分割等和子集](https://leetcode-cn.com/problems/partition-equal-subset-sum)。给定一个只包含正整数的非空数组 nums，请判断是否可以将该数组分割成两个子集，使得两个子集的元素和相等。

这是一个子集问题：选一个子集，让它的元素之和等于原数组和的一半。

#### 朴素思路

暴力搜素（枚举回溯）的代码实现，如下：

```javascript
var canPartition = function(nums) {
  const n = nums.length;
  const sum = nums.reduce((a, b) => a + b);
  if (sum % 2 === 1) return false; // 若和是奇数，则直接返回false

  // 选择一个子集，使其元素之和等于target
  const target = sum / 2;
  let ans = false;

  // 子集问题，递归搜索：判断第pos个位置选or不选
  let seletedSum = 0; // 已选元素之和（状态空间-共享变量）
  const dfs = function(pos) {
    if (ans || seletedSum > target) return; // 剪枝
    if (seletedSum === target) { // 找到答案了
      ans = true;
      return;
    }
    if (pos === n) return; // 叶子结点（正常边界）

    // 本层逻辑：选or不选当前位置的数
    dfs(pos + 1); // 不选
    // 选
    seletedSum += nums[pos]; // 下探时+本层
    dfs(pos + 1);
    seletedSum -= nums[pos]; // 回溯时恢复现场
  };
  dfs(0); // 从位置 0 开始
  return ans;
};
```

> 执行结果：超出时间限制

#### 0/1 背包

子集问题在有和限制的前提下，选数就和 0/1 背包一样。每个数就是一个物品，数的值就是物品的体积，此问题就是求：能否选出一些总体积等于 sum/2 的物品？

此时不用考虑“价值”（最优解问题），而是考虑“体积 M”是否可行（可行性问题）。

按照动态规划的思路进行分析，如下：

1. 重复子问题：`opt[i][j]` 表示从前 i 个数中选出一些数，总和是 j，是否可行？
   * 状态：数 `[i]` 和总和 `[j]`
   * 代表：`opt[i][j]` 是否可行
2. 决策：对于第 i 个数，可以选或者不选
   * 当不选时，`opt[i][j] = opt[i-1][j]`
   * 当选时，`opt[i][j] = opt[i-1][j-nums[i]]`
   * 而 `opt[i][j]` 的值就是这两个分支的逻辑或，即有一个分支是 true 则值就是 true
     * 递推公式：`opt[i][j] = opt[i-1][j] || opt[i-1][j-nums[i]]`
3. 开始递推
   * 默认值：`opt[i][j] = false`
   * 起点：`opt[0][0] = true`
   * 目标：`opt[N][M]` 是否可行

代码实现，如下：

```javascript
var canPartition = function(nums) {
  const n = nums.length;
  const sum = nums.reduce((a, b) => a + b);
  if (sum % 2 === 1) return false; // 若和是奇数，则直接返回false

  // 选择一个子集，使其元素之和等于target
  const target = sum / 2;

  // opt[i][j] 表示从前 i 个数中选出一些数，总和是 j，是否可行？
  let opt = new Array(n + 1); // (N+1)*(M+1)，多申请一个-当保护结点-以方便递推
  for (let i = 0; i <= n; i++) opt[i] = new Array(target + 1).fill(false); // 初始值均为 false（不可达）
  opt[0][0] = true; // 递推起点

  // 从小到大开始递推，先 for 状态，再 for 决策
  for (let i = 1; i <= n; i++) { // [i] 物品-数字
    for (let j = 0; j <= target; j++) { // [j] 总体积-总和
      // 决策：选or不选，有一个分支是 true 就可以
      opt[i][j] = opt[i - 1][j]; // 不选
      if (j >= nums[i - 1]) {
        opt[i][j] = opt[i][j] || opt[i - 1][j - nums[i - 1]]; // 选
      }
    }
  }

  return opt[n][target]; // 直接返回目标状态是否可行
};
```

> 执行结果：通过

优化下代码的空间复杂度，将其从 O(nums.length\*target) 降为 O(target)。如下：

```javascript
var canPartition = function(nums) {
  const n = nums.length;
  const sum = nums.reduce((a, b) => a + b);
  if (sum % 2 === 1) return false; // 若和是奇数，则直接返回false

  // 选择一个子集，使其元素之和等于target
  const target = sum / 2;

  // opt[i][j] 表示从前 i 个数中选出一些数，总和是 j，是否可行？
  let opt = new Array(target + 1).fill(false);
  opt[0] = true;

  // 从小到大开始递推，先 for 状态，再 for 决策
  for (let num of nums) { // [i] 物品-数
    for (let j = target; j >= num; j--) { // [j] 总体积-总和，须倒序遍历，才能拿到之前二维时纯粹的 opt[i-1][j]
      opt[j] = opt[j] || opt[j - num]; // (不选, 选) 两个分支有一个是 true 就可以
    }
  }

  return opt[target];
};
```

> 执行结果：通过

## 完全背包

### 理论部分

与 0/1 背包相比，完全背包的物品不限个数。

完全背包：给定 N <mark style="color:green;">种</mark>物品，其中第 i 种物品的体积是 Vi，价值是 Wi，并且每种物品都有<mark style="color:green;">无数个</mark>。有一个容积为 M 的背包，要求选择一些物品放入背包，使得在总体积不超过 M 的前提下，物品的价值总和最大。

完全背包的递推公式，和 0/1 背包的唯一不同就是：当从第 i 种物品中选择的时候是包含 i 的。

| 背包模型   | 递推公式 `opt[i][j]`                                                                           |
| ------ | ------------------------------------------------------------------------------------------ |
| 0/1 背包 | <p><code>max(opt\[i-1]\[j], opt\[i-1]\[j-Vi] + Wi)</code><br>(不选第 i 个物品, 选择第 i 个物品)</p>    |
| 完全背包   | <p><code>max(opt\[i-1]\[j], opt\[i]\[j-Vi] + Wi)</code><br>(尚未选过第 i 种物品, 从第 i 种物品中选一个)</p> |

直接按照递推公式写，完全背包的代码如下：

```javascript
// 最优化目标：opt[i][j] 表示从前 i 种物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和
let opt = new Array(N + 1); // (N+1)*(M+1)，多申请一个-当保护结点-以方便递推
for (let i = 0; i <= N; i++) opt[i] = new Array(M + 1).fill(-Infinity);
opt[0][0] = 0; // 递推起点

// 从小到大开始递推，先 for 状态，再 for 决策
for (let i = 1; i <= N; i++) { // [i] 物品
  for (let j = 0; j <= M; j++) { // [j] 总体积
    // 决策：选or不选
    opt[i][j] = opt[i - 1][j]; // 不选
    if (j >= V[i]) {
      opt[i][j] = Math.max(opt[i][j], opt[i][j - V[i]] + W[i]); // 选
    }
  }
}

return Math.max(...opt[N]);
```

优化下代码的空间复杂度，将其变为一维，如下：

```javascript
// 最优化目标：opt[i][j] 表示从前 i 种物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和
let opt = new Array(M + 1); // 省略了第一维，从 (N+1)*(M+1) 降低为 (M+1)
opt[0] = 0; // 递推起点

// 从小到大开始递推，先 for 状态，再 for 决策
for (let i = 1; i <= N; i++) { // [i] 物品
  for (let j = V[i]; j <= M; j++) { // [j] 总体积，正序循环即可（便能重复选第 [i] 种物品了）
    opt[j] = Math.max(opt[j], opt[j - V[i]] + W[i]); // max(尚未选过, 选一个)
  }
}

return Math.max(...opt);
```

我们发现，把 0/1 背包算法中的状态 `[j]` 正序循环了之后，就变成完全背包算法了，因为这样就能很方便地实现重复选择第 i 种物品的逻辑了。

看两个例子感受下。

### 例 1：最少硬币个数

> 题目：[零钱兑换的最少硬币个数](https://leetcode-cn.com/problems/coin-change/)。给定一个整数数组 coins（表示不同面额的硬币）和一个整数 amount（表示总金额），计算并返回可以凑成总金额的最少硬币个数。如果没有任何一种硬币组合能组成总金额，就返回 -1。假设每种硬币的数量是无限的。

零钱兑换的问题其实就符合完全背包模型。零钱=物品，面值=体积，价值=1，求最少兑换个数就是求价值的最小值。

用背包的思想来分析这个动态规划的问题，步骤如下：

1. 重复子问题：`opt[i][j]` 表示从前 i 种硬币中凑出总面额为 j 的最少硬币个数
   * 状态：硬币 `[i]` 和总面额 `[j]`
   * 最优化目标：`opt[i][j]` 最少硬币数
2. 决策：对于第 i 种硬币，可以选或者不选
   * 当不选时：`opt[i][j] = opt[i-1][j]`
   * 当选时：`opt[i][j] = opt[i][j-coins[i]] + 1`
   * 而 `opt[i][j]` 的值就取这两个分支的最小值
     * 递推公式：`opt[i][j] = min(opt[i-1][j], opt[i][j-coins[i]] + 1)`
3. 开始递推
   * 默认值：`opt[i][j] = Infinity`
   * 起点：`opt[0][0] = 0`
   * 目标：`opt[N][amount]`

直接套用递推公式，代码如下：

```javascript
var coinChange = function(coins, amount) {
  const n = coins.length;
  // opt[i][j] 表示从前 i 种硬币中凑出总面额为 j 的最少硬币个数
  let opt = new Array(n + 1);
  for (let i = 0; i <= n; i++) opt[i] = new Array(amount + 1).fill(Infinity); // 默认值 Infinity
  opt[0][0] = 0; // 递推起点
  // 开始递推
  for (let i = 1; i <= n; i++) {
    const c = coins[i - 1];
    for (let j = 0; j <= amount; j++) {
      opt[i][j] = opt[i - 1][j];
      if (j >= c && opt[i][j - c] + 1 < opt[i][j]) {
        opt[i][j] = opt[i][j - c] + 1;
      }
    }
  }
  return opt[n][amount] === Infinity ? -1 : opt[n][amount];
};
```

> 执行结果：通过

优化下代码的空间复杂度，如下：

```javascript
var coinChange = function(coins, amount) {
  // opt[i][j] 表示从前 i 种硬币中凑出总面额为 j 的最少硬币个数
  let opt = new Array(amount + 1).fill(Infinity);
  opt[0] = 0;
  for (let c of coins)
    for (let j = c; j <= amount; j++)
      opt[j] = Math.min(opt[j], opt[j - c] + 1);
  // 返回
  return opt[amount] === Infinity ? -1 : opt[amount];
};
```

> 执行结果：通过

### 例 2：硬币组合数

> 题目：[零钱兑换的硬币组合数](https://leetcode-cn.com/problems/coin-change-2/)。给定一个整数数组 coins（表示不同面额的硬币）和一个整数 amount（表示总金额），计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0。假设每种面额的硬币有无限个。

这个问题是完全背包+计数。

1. 重复子问题：`opt[i][j]` 表示从前 i 种硬币中凑出总面额为 j 的硬币组合数
   * 状态：硬币 `[i]` 和总面额 `[j]`
   * 代表：`opt[i][j]` 硬币组合数
2. 决策：对于第 i 种硬币，有两种决策，选或者不选
   * 不选：`opt[i][j] = opt[i-1][j]`
   * 选：`opt[i][j] = opt[i][j-coins[i]]`
   * 而 `opt[i][j]` 的值等于它们之和
     * 递推公式：`opt[i][j] = opt[i-1][j] + opt[i][j-coins[i]]`
3. 开始递推
   * 默认值：`opt[i][j] = 0`
   * 起点：`opt[i][0] = 1`
   * 目标：`opt[N][amount]`

直接按递推公式写，代码如下：

```javascript
var change = function(amount, coins) {
  const n = coins.length;
  // opt[i][j] 表示从前i种硬币中，能凑出总面额为j的硬币组合数
  let opt = new Array(n + 1);
  for (let i = 0; i <= n; i++) {
    opt[i] = new Array(amount + 1).fill(0); // 默认是 0
    opt[i][0] = 1; // 递推起点：[i][0] = 1
  }
  // 开始递推：不选+选
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= amount; j++) {
      opt[i][j] = opt[i - 1][j]; // 不选时
    }
    let c = coins[i - 1];
    for (let j = c; j <= amount; j++) {
      opt[i][j] += opt[i][j - c];
    }
  }
  return opt[n][amount];
};
```

> 执行结果：通过

优化下代码的空间复杂度，如下：

```actionscript
var change = function(amount, coins) {
  let opt = new Array(amount + 1).fill(0);
  opt[0] = 1;
  for (let c of coins)
    for (let j = c; j <= amount; j++)
      opt[j] += opt[j - c];
  return opt[amount];
};
```

> 执行结果：通过

## 总结

背包问题是一类特殊的动态规划问题，它就是在一定的体积限制下取物品，让价值最大化。背包有两个模型，分别是 0/1 背包和完全背包，它们的唯一区别就在于每种物品的个数是 1 个还是无限个。正因如此，它们的递推公式和通用代码之间的区别也不大。

递推公式的区别就在于：当从第 i 种物品中选择的时候<mark style="color:green;">是否包含 i</mark>。

| 背包模型   | 递推公式 `opt[i][j]`                                                                               |
| ------ | ---------------------------------------------------------------------------------------------- |
| 0/1 背包 | <p><code>max(opt\[i-1]\[j], opt\[i-1]\[j-Vi] + Wi)</code> </p><p>(不选第 i 个物品, 选择第 i 个物品)</p>    |
| 完全背包   | <p><code>max(opt\[i-1]\[j], opt\[i]\[j-Vi] + Wi)</code> </p><p>(尚未选过第 i 种物品, 从第 i 种物品中选一个)</p> |

通用代码中，<mark style="color:green;">倒序</mark>循环 `[j]` 时是 0/1 背包，<mark style="color:green;">正序</mark>循环时是完全背包。

```javascript
// opt[i][j] 表示从前 i 种物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和
let opt = new Array(M + 1).fill(-Infinity);
opt[0] = 0;
// 开始递推：先 for 状态，再 for 决策
for (let i = 1; i <= N; i++) {
  for (let j = M; j >= V[i]; j--) {
    // 倒序循环-0/1背包
    // for (let j = V[i]; j <= M; j++) { // 正序循环-完全背包
    opt[j] = Math.max(opt[j], opt[j - V[i]] + W[i]); // max(不选, 选)
  }
}
return Math.max(...opt);
```

背包问题就是“选或者不选”的子集问题，而子集问题适用于所有指数级别的搜索，所以背包的应用非常广泛，比如各种取物品且有体积限制的。它能求解最优解问题 `min, max`、可行性问题 `|= boolean` 以及计数问题 `+=`。