动态规划（背包）
动态规划
动态规划有两个要点，就是状态和转移。
- 状态，很重要的一个点是它能够清晰地描述一个子问题。也就是说我们能够根据我们记录下来的东西能够方便得让我们知道我们在解决什么，要求什么，并且能够通过之前的状态转移过来。在满足这些条件的情况下，我们就可以进一步考虑我们到底需不需要记录这么多状态，是不是可以少记录一些来降低复杂度。
- 转移，就是状态与状态之间的关系。我们需要从一些已知的状态求出一个未知的状态，这个过程就叫转移。转移的快慢很大一部分取决于转移的技巧。例如通过寻找最优决策点的时候有斜率优化、单调队列优化或者四边形不等式优化。有时候，并不是所有的状态都可以通过已知的状态转移过来，很多时候状态是一种类似于方程的形式，这时候就可以使用高斯消元来解决问题，只是复杂度会上升为三次。
背包
相信背包一定是大部分 $\text{OIer}$ 最早接触的一类动态规划问题，但我发现我到最近才对它进行系统的学习，实在是太弱了。它的核心问题是有限制条件的选择物品。而 物品 这个概念也可以被抽象化，一般地，一个或一些物品可以看成一个 价值 对于 重量 的函数 $v = f(w)$。但，物品也可以是很特殊的，例如 $\text{01背包}$ 中物品就是一个价值为 $val$ 重量为 $weight$ 的东西。但它也可以表示成一般的形式，即：
$$v=\begin{cases}val,&w=weight\0,&\text{otherwise}\end{cases}$$
除了直接的形式以外，还有很多题目会隐晦的考察背包问题，这就需要我们将问题的本质抓出来。
$01$ 背包
$01$ 背包其实是所有背包问题的本质。但我们先不讲它为什么是本质，我们先考虑怎么做这个问题。
Sol
首先考虑状态设计。考虑到先选什么后选什么并不会影响最终的答案，因此我们只需设选择了前 $i$ 个即可。另外，显然目前背包的大小也会影响我们能够选什么。这样，我们就有了一个初步的状态设计：在背包大小为 $j$ 的时候选择第 $i$ 个物品的最大价值。
下面开始考虑转移，显然，我在一个状态 $i,j$ 有两种选择，一种是选这个物品，一种是不选，于是就有转移：
$$f_{i,j}=\max{f_{i-1,j},f_{i-1,j-w}+v}$$
于是我们就得到了一个时间复杂度和空间复杂度都为 $O(nV)$ 的算法。
但是，我们注意到这里第 $i$ 层只与 $i-1$ 层有关，因此我们可以开滚动数组来滚掉一维。另外，我们发现后面的状态更新只与前面的有关，因此我们完全可以不要前一维而直接从后往前进行更新，这样就可以完成 $O(V)$ 的空间复杂度，转移方程为：
$$f_{i} = \max{f_i, f_{i-w}+v}$$
伪代码
1 | for i in range(1, n): |
完全背包
与 $01背包$ 不同的是，这里的物品不一定只取一次，而是可以无限制地拿取。这样的物品写成一般的形式就是：
$$v=\begin{cases}k\times val,&w=k\times weight,k\in \mathbb{N}\0,&\text{otherwise}\end{cases}$$
Sol
$O(nV^2)$ 做法
显然，我们除了知道现在背包的容量、取到了哪个物品以外，还需要知道现在的物品到底取多少件，枚举出来之后就很容易得到转移：
$$f_{i,j}=\max_{k=0}^{\infty}{f_{i-1,j-k\times w}+k\times v}$$
这样，对于每一件物品，复杂度是 $O(V\times \frac{V}{w})$，因此总的时间复杂度就是 $O(V^2\sum\frac{1}{w})$，很容易被卡到 $O(nV^2)$。
但是我们考虑，这其实相当于把这个物品拆成很多物品然后做 $01背包$。也就是说，一般地把
$$v=\begin{cases}k\times val,&w=k\times weight,k\in \mathbb{N}\0,&\text{otherwise}\end{cases}$$
拆成：
$$v_i=\begin{cases}i\times val,&w=i\times weight\0,&\text{otherwise}\end{cases}$$
伪代码
1 | for i in range(1,n): |
$O(nV\log V)$ 做法
上述做法其实就是选择一定数量的这个物品，那么这个数量一定可以用二进制表示，也就是说，我们把这个物品拆成 $\log V$ 个，每个表示买 $1$ 个、$2$ 个、$\dots$、$2^{\left\lfloor\log V\right\rfloor}$ 个物品，显然任意数量可以用这些物品表示出来，于是做 $01 背包$ 即可。
形式化的，我们把
$$v=\begin{cases}k\times val,&w=k\times weight,k\in \mathbb{N}\0,&\text{otherwise}\end{cases}$$
拆成：
$$v_i=\begin{cases}2^i\times val,&w=2^i\times weight\0,&\text{otherwise}\end{cases}$$
即可。
伪代码
1 | for t in range(1, log(V)): |
$O(nV)$ 做法
更加快地，我们可以做到时间 $O(nV)$，空间 $O(V)$。
具体地，我们考虑，如果按照 $01背包$ 的做法，但是从前往后地考虑完全背包，显然，如果当前选这个物品更优，我们直接选择即可，然后更新当前的值。当继续更新后面的节点的时候，我们就可以直接继承当前的值，如果继续选择就可以表示选两个、三个以及更多的情形。
这就相当于，我们已经选择了这个物品并加入了贡献，然后继续考虑下一个物品，考虑的时候就正好继承了上一次选的状态。
伪代码
1 | for i in range(1, n): |
多重背包
与完全背包又不一样，多重背包限制了每个物品最多拿多少次，而非可以无限拿，这问题又难了一些。
同样地，我们依旧可以形式化表示这些物品：
$$v=\begin{cases}k\times val,&w=k\times weight,k\in[0,m]\cap\mathbb{Z}\0,&\text{otherwise}\end{cases}$$
Sol
显然，和完全背包一样，我们可以枚举选择多少个该物品。这里不详细展开。
又显然，和完全背包一样，我们可以把选择的物品二进制表示出来。但注意这里二进制拆分不能够把那些大于 $m$ 的状态也表示出来，因此，我们只能取到 $2^{\left\lfloor\log m\right\rfloor-1}$，剩下的我们就再取一个 $m-2^{\left\lfloor\log m\right\rfloor}+1$ 即可。
这里，我们着重讲一下 $O(nV)$ 做法。
显然，根据完全背包的做法，我们发现一个状态 $j$ 可以从 $j-w$，$j-2w$，$\dots$，$j-kw$ 转移过来，而这些数有一个共同特点，就是关于 $w$ 同余。而我们也不难证明，所有的关于 $w$ 余数不同的值都不能在这一层相互转移，于是，我们就可以枚举余数转移。
具体地，关于每一个余数，我们发现一个点 $j$ 只能从 $j-w$ 一直到 $j-mw$ 中最大的转移过来，这显然符合单调队列优化的条件。因此，我们在转移的时候使用一个单调队列优化就可以 $O(nV)$ 通过这个问题。
但是，还有一个细节。就是每一次我们算的 $f_j$ 不能直接用到单调队列中，因为这些值已经加上了我们的贡献 $kv$，因此，加入单调队列的应该是 $f_j-kv$。
伪代码
1 | for i in range(1, n): |
混合背包
显然，上述的三种背包混合起来就都可以转化成多重背包问题。完全背包直接转化成数量只有 $\frac{V}{w}$ 即可。
小节
在完成上述三种背包之后，我们对于背包问题又有了一个基本的了解。进一步拓展，我们发现，如果我们最终求出了动态规划的数组 $f_V$ 这是不是也可以看成一种一般意义上的物品。它表示为一个函数
$$v=f_w$$
这样，我们就能够接着完成一些接下来的背包：
分组背包
Sol
与之前不同的是，现在的物品多了一些组别。而每个组内只能选择一个物品。
状态设计上，因为每个组只能选择一个，因此我们考虑 $f_{i,j}$ 表示前 $i$ 组容量为 $j$ 时的最大价值。状态确实很好地描述了一个子问题，但是我们仍需要考虑的是怎么保证每个组只选一个。
显然，我们仍然需要从大到小枚举容量 $V$，然后，按照一般的 $01背包$ 的思路，我们现在要考虑选择或者不选择。那么，按照分组背包的思路，我们是不是应该考虑选择哪个更合适呢？因此，我们不难得出状态转移方程：
$$f_j=\max_{k\in group_i}{f_{j-w_k}+v_k}$$
伪代码
1 | for i in range(1, k): |
结合我们上文所说的，其实这里的每个组可以被看成一个广义上的物品，我们假设组内有 $s$ 个物品，价值与重量分别为 $v_i$ 和 $w_i$，那么这个物品就可以被写成函数的一般形式：
$$v=\begin{cases}v_i, &w=w_i,i\in[1,s]\cap \mathbb{Z}\0,&\text{otherwise}\end{cases}$$
而这里就是这个一般性的物品在 $01背包$ 时的解法。
显然，这种情况下，如果是完全背包，就没有了组内的限制，显然直接把组拆开即可。
那么我们继续跟着这个思路，如果我们给每个组的背包限制一个容量，那么我们就可以根据一般物品的思路，现在每个组内求出每个组的函数 $v(w)$，然后把 $w$ 重量拆成特殊意义的物品，即每个物品的重量、价值可以表示成二元组 $(w,v(w))$。这样，就可以继续使用背包完成了。
高维背包我不想讲，无非就是 $DP$ 数组上多加几维罢辽。
小节
我们在探讨完一般的背包问题之后，会发现一个有意思的现象。对于刚开始给出的物品 $(w_i, v_i)$，我们可以写成一个函数：
$$f(w) = \begin{cases}v_i, &w=w_i\0,&\text{otherwise}\end{cases}$$
然后，我们通过动态规划之后，把它重新整合成了另一种一般的物品，即最终的动态规划数组 $f_w$。我们发现，在一般的条件下，我们只需要这一维数组就足以描述一个子问题。
进阶：01背包 $k$ 优解
Sol
现在，我们已经不满足于只知道最优解，我们想知道，如果我们有很多人，也就是说，在每个人选的物品不能完全相同的情况下，第 $k$ 个人的最优解是什么。
很显然，最开始的 $f_{j}$ 的状态已经不能满足我们对于新的题目的追求，但是，它仍然是必要的，只不过不充分。既然要求我们求出 $k$ 优解，那么我们不妨设 $f_{j,k}$ 表示背包容量为 $j$ 时的 $k$ 优解。
然后，我们来想想如何转移。对于现在枚举的物品 $i$ 和背包容量 $j$，那么这个背包的容量就应该由 $j-w_i$ 转移过来。而我们要求的是前 $k$ 优解，那么容量为 $j$ 时的 $k$ 优解一定不比 $j-w_i$ 层的劣。根据原来的 $01背包$，会产生 $f_{j,1},\dots,f_{j,k}$ 这些不同的背包价值以及更新上来的 $f_{j-w_i,1}+v_i,\dots,f_{j-w_{i},k}+v_i$ 总共 $2k$ 种价值。这些价值一定包含前 $k$ 优解，而我们又知道 $f_{j}$ 是单调不升的（因为最优解一定比次优解优，以此类推），因此使用类似于归并的方法可以使得转移一次复杂度变成 $O(k)$，因此总的复杂度就是时间 $O(knV)$，空间 $O(kn)$。
正确性证明
所以为什么前 $k$ 优解就一定包含在这 $2k$ 个状态中呢？这就像询问为什么朴素的 $01背包$ 的最优解一定在 $f_j$ 与 $f_{j-w_i}+v_i$ 之中一样。对于背包容量为 $j$ 的问题，在物品 $i$ 已经枚举确定的情况下，我们能且只能通过 $j-w_i$ 的背包容量转移过来，而在 $j-w_i$ 的背包容量的情况下，比 $k$ 优解更劣的解一定不会对当前产生贡献，因为 $f_{j-w_i,1}+v_i$ 到 $f_{j-w_i,k}+v_i$ 已经至少有 $k$ 个，而 $f_{j-w_i,k}\ge f_{j-w_i,k+1}$。同理我们可以知道继承上一层的 $j$ 容量状态最多也只到 $k$ 优。因此这 $2k$ 个状态就决定了现在的 $f_{j,1}$ 到 $f_{j,k}$。
Code【P1858 多人背包】
1 | const int N = 200 + 10; |