背包 DP
背包 DP，正如它的名字，是将问题模型抽象成一个背包，背包有容量，物品拥有体积和价值，要将物品按照一定的限制放入这个背包，从而求解一系列问题。
01 背包：
例 $1$：
有一个容量为 $V$ 的背包有 $n$ 种物品，每种物品有 $v_i$ 的体积和 $w_i$ 的价值，每种物品最多取一个，求能获得的最大价值。
状态：
设 dp$[i][j]$ 表示考虑前 $i$ 个物品，选出物品体积为 $j$ 的最大价值。
状态转移：
$(i,j)\leftarrow(i-1,j-v_i),(i-1,j)$
DP 式子：
For(i,1,n) For(j,v[i],V) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
最后的解即为：dp$[n][V]$。
某一个物品的答案一定是从前面的物品转移来的，而当前的容量之间没有转移关系，所以容量的枚举顺序无影响。
时间复杂度：$O(nV)$
空间复杂度：$O(nV)$
滚动数组优化：
观察到，dp$[i]$ 只与 dp$[i-1]$ 有关，而与 dp$[1],…,$dp$[i-2]$ 无关，同时最后的结果只和 dp$[n][V]$ 有关。也就是同时最多只需要用到两组 dp 数组的第二维，所以 dp 第一维只需要存两个即可。
通常使用 dp$[i\And 1]$ 的方式仅保留 $i$ 和 $i-1$ 的结果。
最后的解即为：dp$[n\And1][V]$。
空间复杂度优化至线性。
在此题的特殊处理：
继续观察，dp$[i][j]$ 会继承 dp$[i-1][j]$ 的答案，即：dp$[i][j]\geq$dp$[i-1][j]$。
所以不妨直接让 dp$[i][j]$ 继承 dp$[i-1][j]$ 的答案（直接共用一个数组）。
新 DP 式子：
For(i,1,n) For(j,v[i],V) dp[j]=max(dp[j],dp[j-v[i]]+w[i])
但是此时会产生新的问题：dp$[j-v[i]]$ 可能是会被修改的，而原式子中的 dp$[i-1][j-v[i]]$ 是固定的，现在的 dp$[j-v[i]]$ 不一一对应 dp$[i-1][j-v[i]]$，它可以从 $dp[j-2\times v[i]]$ 转移。而 dp$[i][j]$ 只能由 dp$[i-1][j-v[i]]$ 转移而不是 dp$[i-1][j-2\times v[i]]$。
通过改变枚举顺序可以避免这一点：
For(i,1,n) FOR(j,V,v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i])
从后往前枚举容量时，保证了用于转移的状态是上一层循环记录的正确的值。
完全背包：
例 $2$：
有一个容量为 $V$ 的背包有 $n$ 种物品，每种物品有 $v_i$ 的体积和 $w_i$ 的价值，每种物品取的个数没有限制，求能获得的最大价值。
状态：
设 dp$[j]$ 表示选出物品体积为 $j$ 的最大价值。
状态转移：
$(j)\leftarrow(j-\lfloor\frac{j}{v_i}\rfloor\times v_i),…,(j-v_i),(j)$
DP 式子：
For(i,1,n) FOR(j,V,1) For(k,0,j/v[i]) dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i])
最后的解即为：dp$[V]$。
枚举顺序与 01 背包一致，仅仅是转移的状态数不同，转移关系一致。
时间复杂度：$O(nV^2)$。
空间复杂度：$O(V)$
优化：
显然，$O(nV^2)$ 是不够优秀的，回顾 01 背包中遇到的问题，从前往后枚举容量时，更新的状态不对应：dp$[j-v[i]]$ 不一一对应 dp$[i-1][j-v[i]]$，它可以从 $dp[j-2\times v[i]]$ 转移。而如果将这个结果递归下去，可以发现，dp$[j]$ 正是从 $(j-\lfloor\frac{j}{v_i}\rfloor\times v_i),…,(j-v_i),(j)$ 这样状态转移，这恰好地符合完全背包的要求。
所以，从后往前枚举容量即可实现完全背包的要求，而不用枚举使用量。
新 DP 式子：
For(i,1,n) For(j,v[i],V) dp[j]=max(dp[j],dp[j-v[i]]+w[i])
时间复杂度：$O(nV)$。
多重背包：
例 3：
有一个容量为 $V$ 的背包有 $n$ 种物品，每种物品有 $v_i$ 的体积和 $w_i$ 的价值，每种物品取的个数为 $a_i$，求能获得的最大价值。
状态：
设 dp$[j]$ 表示选出物品体积为 $j$ 的最大价值。
状态转移：
$(j)\leftarrow(j-a_i\times v_i),…,(j-v_i),(j)$
DP 式子：
For(i,1,n) FOR(j,V,1) For(k,0,min(j/v[i],a[i])) dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i])
时间复杂度：$O(nVa_i)$。
空间复杂度：$O(n)$。
二进制拆分优化：
考虑最后的最优的方案中某物品的选取个数，设为 $x$。若这个物品取 $x$ 是最优，那么只要这个物品能取 $x$ 个就能保证最后解正确。那么，就算这个物品原本是可以取 $2x$ 个的，现在把它取的个数限制成 $x$ 个即可。
可是并无法获知每个物品在最终的答案里是被取几次的。
考虑 $a_i=2^0+2^1+…+2^p+(a_i-2^{p+1}+1)$，将原本可以取 $[0,a_i]$ 次的第 $i$ 个物品，拆分成 $\log{a_i}$ 个固定取 $2^0,2^1,..,2^p,(a_i-2^{p+1}+1)$ 的物品。
引理：用 $2^0,2^1,..,2^p,(a_i-2^{p+1}+1)$ 可以组成 $[1,a_i]$ 之间的任何数。
证明：
用 $2^0,2^1,…,2^p$ 可以组成 $[1,2^{p+1}-1]$ 的任何数。
$[2^{p+1},a_i]$ 之间的数可以用 $a_i-2^{p+1}+1$ 和 $[1,2^{p+1}-1]$ 对应组成。
所以原本一个物品有 $O(a_i)$ 的转移量，而现在只有 $O(\log a_i)$ 的转移量。
时间复杂度：$O(nV\log a_i)$。
单调队列优化：
对于一个转移，其转移个数是确定是 $a_i$ 个。在容量从小到大枚举的过程中，转移的下界也在增大，且转移的个数是确定的，前后两次容量的转移区间仅有头尾不同。这是一种特殊的“滑动窗口”，可以套用单调队列优化 DP 的方式优化多重背包。
$(j)\leftarrow(j-a_i\times v_i),…,(j-v_i),(j)$
$(j+v_i)\leftarrow(j-(a_i-1)\times v_i),…,(j),(j+v_i)$
对于 $(j-(a_i-1)\times v_i),…,(j)$ 部分是一样的，只有 $(j-a_i\times v_i)$ 和 $(j+v_i)$ 是不一样的。
具体不作展开。
时间复杂度：$O(nV)$。
01 背包+完全背包+多重背包：
例 4：
有一个容量为 $V$ 的背包有 $n$ 种物品，每种物品有 $v_i$ 的体积和 $w_i$ 的价值，每种物品有一个类型 $op$，$op=1$ 表示最多取 $1$ 次；$op=2$ 表示可以取无限次；$op=3$ 表示最多取 $a_i$ 次，求能获得的最大价值。
事实上，注意到它们之间仅仅是转移的时候，用到的状态数不太一样。所以只需要根据不同的物品的类型，进行不同的处理转移即可。
时间复杂度：$O(nV)$。
空间复杂度：$O(V)$。
addition：
注意到，上述 DP 过程均使用的是“逆推”，优化也基本基于“逆推”才能进行，如果使用“顺推”不易优化。
原因就是“逆推”给定了“从哪来”的范围，每次只更新当前的状态。如果能比较快地在“从哪来”选择出那个最优的，就可以加快运算速度。对于“顺推”，需要用当前状态去更新多个状态，对于区间修改，是不易维护的（可以，较复杂，对应数据结构的区间修改）。
多维背包：
例 5：
有 $n$ 个任务需要完成，完成第 $i$ 个任务需要花费 $t_i$ 分钟，$c_i$ 的支出。共有 $T$ 的时间和 $C$ 的资金，求最多完成多少任务。
与前文中的背包相比，此背包具有二维代价，而不是一维。
因此需要两层循环枚举容量，其它地方并无二致。
For(i,1,n) FOR(j,T,t[i]) FOR(k,C,c[i]) dp[j][k]=max(dp[j][k],dp[j-t[i]][k-c[i]]+1)
时间复杂度：$O(nTC)$。
空间复杂度：$O(TC)$。
分组背包：
例 6：
有一个容量为 $V$ 的背包有 $n$ 种物品，每种物品有 $v_i$ 的体积和 $w_i$ 的价值，每种物品最多取一个，同时每个物品都属于一个组 $c_i$，一个组内只能选择一个物品。求能获得的最大价值。
同样是转移的方式不同。因为现在的物品是组内选一个，而组间无关。
转移：
$(j)\leftarrow(j-a_{p_1}),(j-a_{p_2}),…,(j-a_{p_c}),(j)$
由组内的任意一个转移。
DP 式子：
For(i,1,n) FOR(j,V,1) For(j,1,cnt[c[i]]) dp[j]=max(dp[j],dp[j-v[p[j]]]+w[p[j]])
因为所有组内的物品数之和还是 $n$，所以时间复杂度不变。
时间复杂度：$O(nV)$。
空间复杂度：$O(V)$。
背包判可行：
例 7：
有一个容量为 $V$ 的背包有 $n$ 种物品，每种物品有 $v_i$ 的体积，每种物品最多取一个，求是否能取出体积之和为 $m$ 的物品。
状态转移与 01 背包一致，需要修改维护的内容。
状态：
设 dp$[x]$ 表示是否能取出体积之和为 $x$ 的物品。
状态转移：
$(x)\leftarrow(x-v_i)$
DP 式子：
For(i,1,n) FOR(j,V,v[i]) dp[j]|=dp[j-v[i]]
初始化：
初始只有 $0$，dp$[0]=1$ 即可。
时间复杂度：$O(nV)$。
空间复杂度：$O(V)$。
bitset 优化：
因为结果只含 $0/1$，容易联想到 bitset。
每一层物品的循环，$v_i$ 是固定的，所以相当于把 dp$[x]$ 整体右移了 $v_i$。
新 DP 式子：
For(i,1,n) temp=dp<<v[i],dp|=temp
对 bitset 整体操作的时间复杂度为 $O(\frac{n}{\omega})$。
时间复杂度：$O(\frac{nV}{\omega})$。
空间复杂度：$O(\frac{V}{\omega})$。
背包求方案数：
例 8：
有一个容量为 $V$ 的背包有 $n$ 种物品，每种物品有 $v_i$ 的体积，每种物品最多取一个，求取出体积之和为 $m$ 的物品的方案数。
同样是状态转移与 01 背包一致，需要修改维护的内容。
状态：
设 dp$[x]$ 表示取出体积之和为 $x$ 的物品的方案数。
状态转移：
$(j)\leftarrow(j-v_i)$
DP 式子：
For(i,1,n) FOR(j,V,v[i]) dp[j]+=dp[j-v[i]]
时间复杂度：$O(nV)$。
空间复杂度：$O(V)$。
多项式卷积：
每一个物品都可以视作一个形式幂级数，$n$ 个物品求方案数等价于 $n$ 个形式幂级数的卷积。
利用形式幂级数的封闭形式，可以做到 $O(V\log V)$。
此处不过多展开。
可撤销性：
背包求方案数的过程具有可撤销性。
例 9：
有一个容量为 $V$ 的背包，每次新加一个物品体积为 $v_i$，或每次删去一个已添加的物品，对于每次操作都求取出物品体积之和为 $m$ 的方案数。
新加物品的操作与前文一致。考虑如何删去一个物品。
实际上，若从多项式卷积的角度，“可撤销性”是容易解释的。
因为撤销一个物品相当于在若干个形式幂级数的卷积里去掉一个，等价于卷积的逆操作，或者称“多项式除法”。是可行的，但是每次的时间复杂度均为：$O(V\log V)$。
考虑 DP。
状态：
设 dp$[x]$ 表示取出体积之和为 $x$ 的物品的方案数。
状态转移：
$(j)\leftarrow(j-v_i)$
DP 式子：
- 添加：
FOR(j,V,v[i]) dp[j]+=dp[j-v[i]] - 删除：
For(j,v[i],V) dp[j]-=dp[j-v[i]]
删除时，同样要保证 dp$[j]$ 减去的是不考虑 v$[i]$ 的方案数，所以 dp$[j-v[i]]$ 要先把 dp$[j-2\times v[i]]$ 的部分减去。因此，删除需要从小到大枚举容量。
单次时间复杂度：$O(V)$。
addition：
先枚举容量和先枚举物品。
实际上，这个问题在于 01 背包和完全背包的比较。
在 01 背包中，每个物品只能选择 $1$ 次或者 $0$ 次，若是先枚举容量，每一次都枚举物品，那么无法确定某一个物品是否在前面的枚举中使用过。而完全背包对选择的次数没有限制，所以也就不用确定是否在前面的枚举中使用过。所以，对于完全背包，是可以先枚举容量，再枚举物品的；对于 01 背包，是不可以先枚举容量，再枚举物品的。其它背包过程同理，若物品的使用次数有限制，则不能先枚举容量。而需要先枚举物品，使得物品之间的选择相互独立且考虑完备。