# 背包问题

> source: 文章/knapsack/index.md

背包问题是动态规划中非常经典的一类模型。它的核心问题是：给定若干物品，每个物品有重量和价值，在背包容量有限的情况下，如何选择物品，使得总重量不超过容量，同时总价值最大。

从状态转移的角度看，背包问题关心的是「当前物品选不选、选几次」；从生成函数的角度看，背包问题也可以理解为多项式乘法中某一项系数的含义。


## 0-1 背包

0-1 背包中，每个物品最多只能选择一次。

假设有 $n$ 个物品，第 $i$ 个物品的重量为 $w_i$，价值为 $v_i$，背包容量为 $W$。目标是在总重量不超过 $W$ 的前提下，让总价值最大。

例如：

| 物品 | 重量 | 价值 |
| :--: | :--: | :--: |
| 物品 0 | 1 | 15 |
| 物品 1 | 3 | 20 |
| 物品 2 | 4 | 30 |

背包最大容量为 $4$。

### 二维 DP

定义状态：

$$
dp[i][j]
$$

表示只考虑前 $i$ 个物品，在背包容量为 $j$ 时可以获得的最大价值。

对于第 $i$ 个物品，有两种选择：

- 不选第 $i$ 个物品，价值为 $dp[i - 1][j]$
- 选第 $i$ 个物品，价值为 $dp[i - 1][j - w_i] + v_i$

因此状态转移方程为：

$$
dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - w_i] + v_i)
$$

如果 $j < w_i$，说明当前容量放不下第 $i$ 个物品，只能不选：

$$
dp[i][j] = dp[i - 1][j]
$$

这个状态转移的本质是：当前层 $i$ 的结果只依赖上一层 $i - 1$。因为每个物品最多只能使用一次，所以选第 $i$ 个物品时，剩余容量 $j - w_i$ 对应的也必须是上一层的结果。

### 一维优化

二维 DP 中，当前状态只依赖上一层，因此可以压缩成一维数组。

定义：

$$
dp[j]
$$

表示容量为 $j$ 时能够获得的最大价值。

状态转移为：

$$
dp[j] = \max(dp[j], dp[j - w_i] + v_i)
$$

代码如下：

```cpp
vector<int> dp(W + 1, 0);

for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}
```

这里容量 $j$ 必须倒序枚举。

原因是 0-1 背包中每个物品只能使用一次。如果正序枚举，$dp[j - w_i]$ 可能已经在本轮被当前物品更新过，再用它更新 $dp[j]$，就相当于重复使用了第 $i$ 个物品。

倒序枚举可以保证 $dp[j - w_i]$ 仍然是上一轮物品处理完后的状态。

一句话记住这件事：**倒序相当于看完历史记录再写，不会读到自己刚写下的东西；正序则是边读边写，可能读到自己刚写的内容，污染了历史记录。**

## 完全背包

完全背包中，每种物品可以选择无限次。

它的转移形式和 0-1 背包很像：

$$
dp[j] = \max(dp[j], dp[j - w_i] + v_i)
$$

区别在于容量 $j$ 要正序枚举。

```cpp
vector<int> dp(W + 1, 0);

for (int i = 0; i < n; i++) {
    for (int j = w[i]; j <= W; j++) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}
```

为什么完全背包要正序？

假设只有一种物品，重量 $w = 2$，价值 $v = 3$，背包容量 $W = 4$。

初始化：

```text
dp = [0, 0, 0, 0, 0]
```

正序枚举容量：

```text
j = 2: dp[2] = dp[0] + 3 = 3
j = 4: dp[4] = dp[2] + 3 = 6
```

这里 $dp[2]$ 已经使用了当前物品，再用它更新 $dp[4]$，正好表示当前物品可以被重复使用。

因此：

| 类型 | 容量枚举方向 | 含义 |
| :--: | :--: | :-- |
| 0-1 背包 | 倒序 | 防止同一物品重复使用 |
| 完全背包 | 正序 | 允许同一物品重复使用 |

## 多重背包

多重背包中，每种物品最多可以选择 $c_i$ 次。

第 $i$ 种物品有：

- 重量 $w_i$
- 价值 $v_i$
- 数量 $c_i$

一种直接做法是枚举当前物品选多少个：

```cpp
vector<int> dp(W + 1, 0);

for (int i = 0; i < n; i++) {
    for (int j = W; j >= 0; j--) {
        for (int k = 1; k <= c[i] && k * w[i] <= j; k++) {
            dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);
        }
    }
}
```

这种做法的复杂度较高：

$$
O(W \sum c_i)
$$

### 二进制拆分

多重背包常用二进制拆分优化。

如果某种物品有 $13$ 个，可以拆成：

```text
1, 2, 4, 6
```

因为：

$$
13 = 1 + 2 + 4 + 6
$$

这样可以把一种多重物品拆成若干个 0-1 物品。

例如某种物品的重量为 $w$，价值为 $v$，数量为 $13$，可以拆成：

| 拆分数量 | 新重量 | 新价值 |
| :--: | :--: | :--: |
| 1 | $w$ | $v$ |
| 2 | $2w$ | $2v$ |
| 4 | $4w$ | $4v$ |
| 6 | $6w$ | $6v$ |

然后对这些拆出来的物品做 0-1 背包即可。

优化后的复杂度约为：

$$
O(W \sum \log c_i)
$$

二进制拆分的关键在于：任意不超过 $13$ 的选择数量，都可以由 $1, 2, 4, 6$ 中的若干项组合出来。

## 计数型背包

有些背包问题不是求最大价值，而是问：

- 能否凑出重量 $x$
- 有多少种方案可以凑出重量 $x$

这类问题可以使用布尔 DP 或计数 DP。

### 判断能否凑出重量

定义：

$$
dp[j]
$$

表示是否可以凑出重量 $j$。

初始化：

```cpp
dp[0] = true;
```

0-1 背包写法：

```cpp
vector<bool> dp(W + 1, false);
dp[0] = true;

for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {
        dp[j] = dp[j] || dp[j - w[i]];
    }
}
```

状态转移可以写成：

$$
dp[j] \leftarrow dp[j] \lor dp[j - w_i]
$$

### 统计方案数

定义：

$$
dp[j]
$$

表示凑出重量 $j$ 的方案数。

初始化：

```cpp
dp[0] = 1;
```

0-1 背包计数写法：

```cpp
vector<long long> dp(W + 1, 0);
dp[0] = 1;

for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {
        dp[j] += dp[j - w[i]];
    }
}
```

状态转移为：

$$
dp[j] = dp[j] + dp[j - w_i]
$$

这个式子可以理解为：

- 原来就能凑出 $j$ 的方案，保留
- 如果能凑出 $j - w_i$，那么再加上当前物品，就能凑出 $j$

## 生成函数视角

背包问题也可以从生成函数的角度理解。

对于一个重量为 $w$ 的 0-1 物品，它只有两种选择：

- 不选：贡献 $1$
- 选：贡献 $x^w$

所以这个物品对应的生成函数是：

$$
1 + x^w
$$

如果有重量分别为 $2, 3, 5$ 的物品，那么整体生成函数为：

$$
(1 + x^2)(1 + x^3)(1 + x^5)
$$

展开后，如果 $x^k$ 的系数非零，说明存在一种方案可以凑出重量 $k$。

更进一步，$x^k$ 的系数表示凑出重量 $k$ 的方案数。

比如 $x^5$ 可能来自：

- 选择重量 $2$ 和重量 $3$ 的物品
- 直接选择重量 $5$ 的物品

因此 $x^5$ 的系数就是凑出重量 $5$ 的方案数量。

### 和 DP 的关系

0-1 背包的计数转移是：

$$
dp[j] = dp[j] + dp[j - w_i]
$$

这本质上等价于不断乘上：

$$
1 + x^{w_i}
$$

也就是：

$$
f(x) \leftarrow f(x)(1 + x^{w_i})
$$

每处理一个物品，就相当于把当前多项式乘上这个物品对应的生成函数。

### 完全背包的生成函数

完全背包中，每个物品可以选择无限次。

对于重量为 $w$ 的物品，可以选择：

```text
0 个、1 个、2 个、3 个、……
```

对应生成函数为：

$$
1 + x^w + x^{2w} + x^{3w} + \cdots
$$

也就是：

$$
\frac{1}{1 - x^w}
$$

因此完全背包整体可以表示为：

$$
\prod_i \frac{1}{1 - x^{w_i}}
$$

从这个角度看，背包 DP 其实是在维护多项式系数。某些计数问题还可以进一步转化为多项式乘法问题，并使用 FFT 或 NTT 优化。

## 子集和问题（部分和问题）

第一次碰到这个问题是在『アルゴリズムとデータ構造　大槻兼介(Otsuki kensuke)』P36，下面是原题的描述：

> N個の正の整数 $a_0, a_1, \cdots, a_{N-1}$ と正の整数Wが与えられます. $a_0, a_1, \cdots, a_{N-1}$ の中から何個かの整数を選んで総和を W とするとができるかどうかを判定してください.

翻译一下就是：有 `n` 个正整数元素的数组 `a[]`，每次从中取若干个元素 `a[i]`，问是否存在子集的和等于 W

这里我把问题加强，改为：输出所有可以使这些元素之和为 `W` 的数组 `vector<vector<int>>`。对于这个题我一共看到三种方法：

1. 参考 [leetcode 77. 组合](https://leetcode.cn/problems/combinations/description/)，回溯算法找出所有的子数组，然后对这些子数组一个个验证。这种方法属于暴力破解，容易实现就是复杂度有点高
2. 二进制 bit 演算，很聪明的一种方法，原书中提到的一种算法
3. 深搜回溯，这类题的一般解法，适合暴力遍历所有情况

因此我在这里先列出一般解法：

```c++
// 部分和问题 Subset Sum Problem
#include<iostream>
#include<vector>
using namespace std;

int w = 10;
vector<int> a = {2, 3, 1, 6, 7, 4};
vector<vector<int>> res;

void dfs(int index, int current_sum, vector<int>& path, int n, vector<int> a) {
  if (current_sum > w) return;
  if (current_sum == w) {
    res.push_back(path);
    return;
  }
  for (int i = index; i < n; i++) {
    path.push_back(a[i]);
    dfs(i + 1, current_sum + a[i], path, n, a);
    path.pop_back();
  }
}

int main() {
  vector<int> path = {};
  dfs(0, 0, path, a.size(), a);

  cout << "查询结果:" << endl;
  if (res.size()) {
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
          if ( j == res[i].size() -1) cout << res[i][j];
          else cout << res[i][j] << "->";
        }
        cout << endl;
      }
  }
  else {
    cout << "没有满足条件的子集" << endl;
  }
}
```

执行结果：

```bash
查询结果:
2->3->1->4
2->1->7
3->1->6
3->7
6->4
```

原书中提供了一种动态规划的算法，理解起来颇有难度，但代码非常简洁，可惜只能使用于寻找是否存在的情况，如果要枚举所有的情况，动态规划在这里就不适用了

### 递归与递推

对于动态规划，我们有两种表现方法：`递归` 和 `递推`

- 我们在第一次接触动态规划的时候学习的斐波那契数列的通项求法基本上都是以递归开始的，函数的返回值为自身，不断递归直到*回归*到初始条件，因此叫做递归
- 递推则稍有不同，这种写法的函数通常没有返回值，而是将执行获得的信息保存在一个外部数组或其它结构中，比如在 0-1 背包问题中通过更小的前项如 `dp[0] == True` 来得知 `dp[1] == True`（这里只是假设），进而推导出数值更大的情况，直至我们想要的场景

## 分割等和子集（416）

[leetcode 416. 分割等和子集](https://leetcode.cn/problems/partition-equal-subset-sum/submissions/631282269/)：0-1 背包问题

这个问题跟上面的其实是一样的，我们只需要找一个子集，它的所有元素之和为 `sum(nums) / 2`，这里正是只要求**找到**，而不是要求找出全部分法

### 回溯法（暴力破解所有可能的解）

如果使用上述的回溯法：

```python
def canPartition(self, nums: List[int]) -> bool:
    half_sum = sum(nums) / 2
    if sum(nums) % 2:
        return False

    exist = False
    path = []
    def dfs(index, current_sum) -> None:
        nonlocal exist
        if current_sum > half_sum:
            return
        if current_sum == half_sum:
            exist = True
            return
        for i in range(index, len(nums)):
            path.append(nums[i])
            dfs(i + 1, current_sum + nums[i])
            path.pop()

    dfs(0, 0)
    return exist
```

并不是不能做，但是面对较大的测试用例时会超时，因为回溯法枚举所有子集的分支数是 $O(2^n)$，因此最好采用 01 背包问题的动态规划

### 二维 dp 数组写法

```python
def canPartition(self, nums: List[int]) -> bool:
    target = sum(nums) // 2
    if sum(nums) % 2:
        return False

    dp = [[False] * (target + 1) for _ in range(len(nums))]
    for i in range(len(dp)):
        dp[i][0] = True
    dp[0][nums[0]] = True
    for i in range(1, len(nums)):
        num = nums[i]
        for curr_target in range(1, target + 1):
            if curr_target < num:
                dp[i][curr_target] = dp[i - 1][curr_target]
            if curr_target >= num:
                dp[i][curr_target] = dp[i - 1][curr_target] or dp[i - 1][curr_target - num]
    return dp[len(nums) - 1][target]
```

定义的 `dp[i][target]` 第一次接触这种动态规划的话可能很难理解，其中的 `[i]` 代表我们从数组 `nums` 中取若干个 `[0, i]` 范围内的元素 `num`，这个范围随着我们 dp 的进行范围越来越大，因为在程序运行的前期我们有着太多未知的状态，先从简单的状态（小的集合）开始一步步递推出复杂状态（集合元素变多）的值。因此，我们在内循环中采用的是正向遍历的方式（这与后面的一维数组方法相反），采用二维数组动态规划的方法允许我们知道使用前 `i + 1` 个元素组成的子集分别能组成怎样的和，全部都记录在二维 dp 数组中

状态转移就不细说了，各种答案和视频里都满是，我写在这里也没多大意义，不过要注意一下 Python 里面用的 `or`

### 一维 dp 数组写法

```python
def canPartition(self, nums: List[int]) -> bool:
    half_sum = sum(nums) // 2
    if sum(nums) % 2:
        return False

    dp = [False] * (half_sum + 1)
    dp[0] = True
    for num in nums:
        for total in range(half_sum, num - 1, -1):
            dp[total] = dp[total] or dp[total - num]
    return dp[half_sum]
```

一维写法和二维相比思路刚好是相反的，二维写法是从小的子集可能的情况开始推算，递推到复杂的情况

而一维写法则是从复杂的情况开始，一个一个查看元素，然后对一个具体元素分析的时候要注意采用了倒序遍历，这是为了防止元素出现重复使用。比如某一数组的 `target == 6` 而当前遍历的 `num = 3`，我们来看看会发生什么情况

正向遍历下 `range(num, target)`，我们一开始就确定了 `dp[3] -> dp[3 - 3] -> dp[0] == True`，而当遍历到 `dp[6] -> dp[6 - 3] = dp[3]`，此时我们对枚举出来的 `num` 使用了两次，为什么使用了两次？因为我们在这个外循环中使用了两次减法，而减法在这里意味着我们已经选中该 `num`，并且加入到背包，从而背包的容量相应地减小。01 背包问题不允许我们对同一元素使用两次，这也正是 **01** 背包名称的来源，要么你不选，要么你只能选一次。而倒序遍历是一定不会发生重复使用的问题的，因为复杂的状态在我们知道简单的状态之前是不可能被推导出来的，因此在内部循环中只会被掠过

## 零钱兑换（完全背包）

[leetcode 322. 零钱兑换](https://leetcode.cn/problems/coin-change/description/)

解题思路和上面的 0-1 背包非常相似，但我一开始想着用二维数组进行动态规划，搞了老半天发现行不通，只需要给定一个值 `dp[curr_amount]` 让它存储最优解的次数即可，由于这个题硬币数是动态变化的，一时摸不着头脑也很正常，但我们先来看一道高中递归题

[leetcode 70. 爬楼梯](https://leetcode.cn/problems/climbing-stairs/)

```python
def climbStairs(self, n: int) -> int:
  if n == 1:
    return 1
  dp = [0 for _ in range(n + 1)]
  dp[1] = 1
  dp[2] = 2
  for i in range(3, n + 1):
    dp[i] = dp[i-1] + dp[i-2]
  return dp[n]
```

在这里只要搞清楚状态转移的来源，当前状态所处的位置的全部可能性来源于上一个状态的全部可能性，上一个状态则明显只有两种情况，一个台阶下或两个台阶下。以此递归即可获得所有可能性

现在稍微改一下数字，允许一次爬 2 个台阶或 3 个台阶，求到第 n 阶所需的最少次数。这看起来就和我们的原题很像了

```python
# 默认 n > 3
dp = [float('inf') for _ in range(n + 1)]
dp[0] = 0
dp[2] = 1
dp[3] = 1
for i in range(4, n + 1):
  dp[i] = min(dp[i-2] + 1, dp[i-3]) + 1
return dp[n]
```

现在我们把允许一次爬的台阶数变成若干个，存入数组：`[1, 2, 5, ...]` 这样就变成了上面的那道原题。完全背包允许我们无限次地取用数组内的元素

```python
class Solution:
  def coinChange(self, coins: List[int], amount: int) -> int:
    coins.sort()
    dp = [float('inf') for _ in range(amount + 1)]
    dp[0] = 0
    for coin in coins:
      for curr_amount in range(coin, amount + 1):
        dp[curr_amount] = min(dp[curr_amount], dp[curr_amount - coin] + 1)
    return -1 if dp[amount] == float('inf') else dp[amount]
```

由于数组元素变成了若干个，没有办法像上面那样直接写出来了，只能遍历每一种 `coin`，更新最小值，具体思路参考 0-1 背包

## 总结

背包问题的核心在于状态定义和枚举顺序。

| 类型 | 每个物品可选次数 | 常见转移 | 容量枚举 |
| :--: | :--: | :-- | :--: |
| 0-1 背包 | 0 或 1 次 | $dp[j] = \max(dp[j], dp[j - w] + v)$ | 倒序 |
| 完全背包 | 无限次 | $dp[j] = \max(dp[j], dp[j - w] + v)$ | 正序 |
| 多重背包 | 最多 $c_i$ 次 | 枚举数量或二进制拆分 | 通常转成 0-1 |
| 计数背包 | 统计方案数 | $dp[j] += dp[j - w]$ | 根据题意决定 |
| 生成函数 | 多项式建模 | 系数表示方案数 | 可结合 FFT/NTT |

一句话记忆：

```text
0-1 背包倒序，防止重复使用；
完全背包正序，允许重复使用；
多重背包拆分，转化为 0-1；
计数背包求方案数；
生成函数把背包看成多项式乘法。
```
