# 背包DP
## 问题描述
### 基本背包问题
背包问题（Knapsack Problem）描述的是有容量约束的情况下，求考虑了所有物品（大小价值各异）之后的最优解或解的个数。\[[背包问题九讲](https://github.com/tianyicui/pack/blob/master/V2.pdf)]
首先来总结，如果我们要求的是**背包中能装的最大价值**。我们用以下变量来表示：
* $$v\_i$$ ：物品$$i$$ 的大小
* $$w\_i$$ ：物品 $$i$$ 的价值
* $$V:$$ 背包总容量
* $$f\[j]$$ **表示容量为** $$j$$ **的背包的答案**，最后返回答案 $$f\[V]$$。
两种基本的背包问题：
1. **0-1背包**：每个物品只能拿一次
2. **完全背包**：每个物品能拿无限次
| 背包方法 | 转移方程（空间压缩后） | 容量$$j$$的遍历顺序 |
| ----- | ---------------------------------------- | ------------------------------------ |
| 0-1背包 | $$f\[j] = \max\_{i}(f\[j-v\_i] + w\_i)$$ | $$j\text{ 倒序 } V \text{ to } v\_i$$ |
| 完全背包 | $$f\[j] = \max\_{i}(f\[j-v\_i] + w\_i)$$ | $$j\text{ 正序 } v\_i \text{ to } V$$ |
```python
# 0-1背包：因为利用到本行信息，倒序保证安全更新
for n in nums:
for j in range(V, n-1, -1):
# 完全背包：因为利用到上一行信息，正序保证及时更新
for n in nums:
for j in range(n, V+1):
```
在循环中是业务逻辑，有时候我们不是求最大最小值，而是求可行性或者方案数。
```python
f[j] = max(f[j], f[j-n]+v) # 最值
f[j] += f[j-n] # 方案数
f[j] |= f[j-n] # 可行性
```
**其中0-1背包和完全背包的转移方程是一样的，唯一区别是容量变量** $$j$$ **的遍历方向。**
### **遍历方向解释**
能够这样做的原因是因为转移方程依赖哪一行的结果，之后我们看了二维（空间压缩前的转移方程）就明白了，图示如下：
* **0-1背包**：因为利用到本行信息，倒序保证安全更新
* **完全背包**：因为利用到上一行信息，正序保证及时更新
{% hint style="info" %}
乍一看背包问题有可能觉得是用DFS求解，每次考虑是否装入某个物品。虽然用了记忆化优化后也能有效求解，但我觉得用背包DP求解会更容易理解。
{% endhint %}
初始化 $$f$$ 有两种情况：
* 求背包中能装的最大价值，初始$$f\[0, ..., V]=0$$
* 求**装满**背包的最大价值，初始$$f\[0]=0, f\[1, ..., V]=-\infty$$
* 或者可行性解决初始化： $$f\[0]=\text{True}, f\[1, ..., V]=\text{False}$$
* 可以这么考虑：考虑了0个物品后，什么都不装 = 装满容量为0的背包
### 延伸背包问题
1. **多维费用背包**：如果背包有多种容量限制（比如长和宽），每个物品有多个维度体积，那么可以“费用“这个维度可以扩展开来。如果每个物品只能拿一次，维度=2，那么就是二维费用0-1背包问题，
2. **分组背包**：如果所有物品被划分成 $$K$$ 组，每组最多只能拿一个物品
| 背包方法 | 转移方程（空间压缩后） | 容量$$j$$的遍历顺序 | |
| ------- | ----------------------------------------------------- | ------------------------------------------------------------------------ | ------------------------------------------------------------------------------------------------------------------------------- |
| 二维0-1背包 | $$f\[j]\[k] = \max\_{i}(f\[j-v\_i]\[k-u\_i] + w\_i)$$ | $$j\text{ 倒序 } V \text{ to } v\_i \ k\text{ 倒序 } V \text{ to } u\_i$$ | |
| 分组背包 | $$f\[j] = \max(f\[j-v\_i] + w\_i) \\ | \text{item}\_i \in \text{group } k$$ | k\text{ 正序 } 1 \text{ to } K
j\text{ 倒序 } V \text{ to } 0
|
```python
# 考虑元素之间顺序的组合问题
for j in range(1, V+1):
for n in nums:
# 二维费用0-1背包：
for n, n2 in nums:
for j in range(m, n1-1, -1):
for k in range(n, n2-1, -1):
# 分组背包：第三层循环顺序保证每组最多拿一个物品
for k in range(K):
for j in range(V, -1, -1):
for n in nums[k]:
```
## 例题
### 0-1背包
空间压缩前的转移方程：
$$f\[i]\[j] = \begin{cases} \text{不拿物品}i&:& f\[i-1]\[j] \ \text{拿物品}i &:& f\[i-1]\[j-v\_i] + w\_i \ \end{cases}$$
* [目标和](https://leetcode-cn.com/problems/target-sum/)：转化问题以后为**0-1背包方案数**问题。每个物品只能拿一次，有几种装满背包的方案？
* [分割等和子集](https://leetcode-cn.com/problems/partition-equal-subset-sum/)：转化后为**0-1背包可行性**问题。每个物品只能拿一次，是否能正好装满背包。
* [最后一块石头的重量 II](https://leetcode-cn.com/problems/last-stone-weight-ii/)：转化后为**0-1背包最小值**问题。
{% tabs %}
{% tab title="目标和" %}
```python
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
```
```python
def findTargetSumWays(nums, target):
# n0+n1+...-n3-n4 = target =>
# 2*(n0+n1+...) = target + sum
# 0-1 knapsack with capacity = (target+sum) // 2
s = sum(nums)
if (target+s)&1 or target>s: return 0
V = (target + s) >> 1
f = [1] + [0]*V
for n in nums:
for j in range(V, n-1, -1):
f[j] += f[j-n]
return f[-1]
```
{% endtab %}
{% tab title="分割等和子集" %}
```python
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
```
```python
def canPartition(nums):
s = sum(nums)
if s&1: return False
V = s >> 1
f = [True] + [False]*V
for n in nums:
for j in range(V, n-1, -1):
f[j] |= f[j-n]
return f[-1]
```
{% endtab %}
{% tab title="最后一块石头的重量 II" %}
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
* 如果 x == y，那么两块石头都会被完全粉碎；
* 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
```python
def lastStoneWeightII(nums):
# s1-s2+s3-s4+... = sum(s) - 2*(s2+s4+...)
# maximize subarry sum S=s2+s4+...
# s2 S> 1
# 0-1 knapsack with capacity=V
f = [0 for _ in range(V+1)]
for n in nums:
for j in range(V, n-1, -1):
f[j] = max(f[j], f[j-n]+n)
return s-f[-1]*2
```
{% endtab %}
{% endtabs %}
### 完全背包
空间压缩前的转移方程：唯一的区别在于拿了物品 $$i$$ 以后不急着增加 $$i$$，因为你还有机会拿$$i$$。
$$f\[i]\[j] = \begin{cases} \text{不拿物品}i&:& f\[i-1]\[j] \ \text{拿物品}i &:& f\[i]\[j-v\_i] + w\_i \ \end{cases}$$
* [零钱兑换](https://leetcode-cn.com/problems/coin-change/)：**完全背包最小值**
* [零钱兑换 II](https://leetcode-cn.com/problems/coin-change-2/)：**完全背包方案数**
* [完全平方数](https://leetcode-cn.com/problems/perfect-squares/)：**完全背包最小值**
* [组合总和 Ⅳ](https://leetcode-cn.com/problems/combination-sum-iv/)：**考虑物品顺序的完全背包方案数**。每个物品可以重复拿，有几种装满背包的方案？
{% tabs %}
{% tab title="零钱兑换" %}
```python
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
```
```python
def coinChange(nums, V):
f = [0] + [float('inf')]*V
for n in nums:
for j in range(n, V+1):
f[j] = min(f[j], f[j-n]+1)
return f[-1] if f[-1]=0: f[j] += f[j-n]
return f[-1]
```
{% endtab %}
{% endtabs %}
### 二维费用0-1背包
$$f\[i]\[j]\[k] = \begin{cases} \text{不拿物品}i&:& f\[i-1]\[j]\[k] \ \text{拿物品}i &:& f\[i-1]\[j-v\_i]\[k-u\_i] + w\_i \ \end{cases}$$
* [01 字符构成最多的字符串](https://leetcode-cn.com/problems/ones-and-zeroes/)：**多维费用的 0-1 背包最大值**，有两个背包大小，0 的数量和 1 的数量。
* [盈利计划](https://leetcode-cn.com/problems/profitable-schemes/)：**多维费用的 0-1 背包最大值**
{% tabs %}
{% tab title="01 字符构成最多的字符串" %}
```python
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，
该子集中 最多 有 m 个 0 和 n 个 1 。
输入：strs = ["10", "0001", "111001", "1", "0"],
m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是
{"10","0001","1","0"} 因此答案是 4 。
其他满足题意但较小的子集包括{"0001","1"} 和 {"10","1","0"} 。
{"111001"}不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
```
```python
def findMaxForm(strs, m, n):
f = [[0]*(n+1) for _ in range(m+1)]
for s in strs:
c1, c0 = s.count("0"), s.count("1")
for i in range(m, c1-1, -1):
for j in range(n, c0-1, -1):
f[i][j] = max(f[i][j],
f[i-c1][j-c0]+1)
return f[-1][-1]
```
{% endtab %}
{% tab title="盈利计划" %}
```python
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，
它要求 group[i] 名成员共同参与。
如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为盈利计划。
并且工作的成员总数最多为 n 。
有多少种计划可以选择？
输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，
或仅完成工作 1 。总的来说，有两种计划。
```
```python
def profitableSchemes(n, minProfit, group, profit):
f = [[0]*(n+1) for _ in range(minProfit+1)]
f[0][0] = 1
for v, p in zip(group, profit):
for i in range(minProfit+p, p-1, -1):
for j in range(n, v-1, -1):
f[min(minProfit, i)][j] += f[i-p][j-v]
return sum(f[-1]) % (10**9+7)
```
{% endtab %}
{% endtabs %}
### 分组背包
$$f\[k]\[j] = \begin{cases} \text{不拿第k组}&:& f\[k-1]\[j] \ \text{拿第k组}i &:& f\[k-1]\[j-v\_i] + w\_i | \text{item}\_i \in \text{group } k \ \end{cases}$$
[掷骰子的N种方法](https://leetcode-cn.com/problems/number-of-dice-rolls-with-target-sum/)：每一组是一个骰子，每个骰子只能拿一个体积为1到6的物品
```python
这里有 d 个一样的骰子，每个骰子上都有 f 个面
分别标号为 1, 2, ..., f。
我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。
如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况.
输入：d = 1, f = 6, target = 3
输出：1
```
```python
def numRollsToTarget(n, maxpoints, V):
MOD = 10**9 + 7
f = [1] + [0]*V
for i in range(n):
for j in range(V, i-1, -1):
f[j] = 0
for k in range(1, min(maxpoints, j)+1):
f[j] = (f[j] + f[j-k]) % MOD
return f[-1]
```