背包问题的总结

Daniel_yuan · 2020-05-29 18:37:47 · 个人记录

与背包相关的动态规划问题

         在整个动态规划问题中，背包问题的占比是相当大的。

         从刚学 OI，到冲刺 HNOI，都可以找到与当前水平相对应的背包题目（虽然可能套了一些别的东西）。

         故在此记录一些有关背包的技巧。

多重背包

         对于多重背包，有两种优化，一种是单调队列，一种是二进制分组。前者的复杂度是 O(n\times V) ，后者的复杂度是 O(n\log n\times V) 。

         两者各有千秋，从复杂度上看，前者是更优的，但是在变式上的实用性上看，后者更加有用。因为后者相当于把问题转化成了一个 01 背包的问题，而有些算法仅适用于 01 背包。

         具体的，二进制分组是把一个有 a_i 个的物品 x，分解成 k+1 个物品，其中前 k 个物品都是 2^i 个 x，最后一个物品的个数是剩下的常数 C 个 x。这样对于任意一种选取 x 的方案，都可以用这 k+1 个物品拼起来。最后就把多重背包转化成了 01 背包。

多重背包的小 trick 1

         有这么一个例题：你有一个背包，容量为 V。给你 n 个物品，每个物品的花费是 c_i ，一个物品的价值是 f(c_i) ，f 是给出的一个函数，且题目保证 \sum c_i \leq S ，求能获得的最大价值。n\leq 10^5, V \leq 10^5 ,S \leq 10^5 。1s。

         乍一看是个 01 背包，不过这样的话复杂度是 O(n\times V) 的，显然会炸。但是仔细一想，只可能有 \sqrt{n} 级别个不同的数字，因为方程 \frac{(1+x)x}{2}=n 的正整数解是 \frac{-1+\sqrt{1+8n}}{2}，这是 \sqrt{n} 级别的数。而题目保证物品花费相同的价值相同，那么就可以把花费相同的合并，使其变成一个多重背包，并且使用单调队列优化，这样可以优化到 \sqrt{n} \times V。

多重背包的小 trick 2 \& 3

         有这么一个例题：你有一个背包，容量为 V。给你 n 种物品，每种物品 cnt_i 个，每种物品的花费是 c_i，每种物品的价值是 w_i，求能获得的最大价值。w_i\leq n\leq 50,\quad cnt_i,V,c_i\leq 10^9。

         首先可以观察到价值很小，花费很大。所以对于这种类型的背包，可以考虑把 DP 状态反过来：设 f[i][j] 表示前 i 个物品获得的价值为 j，所需要的最小花费是多少，转移的时候还是枚举第二维，即 f[i][j]=\min(f[i][j],f[i-1][j-w[i]]+c[i])。这样可以大大减小状态数，以达到减小时空复杂度的目的。

         不过对于这道题而言，复杂度还是很高，考虑继续优化。刚开始学习背包的时候，可能会有贪心的想法，即优先选择单位价格最低的物品，选到不能选了再选第二低的物品……以此类推，不过这个算法在当时是个错误的算法，因为选择物品会使背包容量“变小”，这是有后效性的，但是这个思想可以用到这个题目里面来。可以发现，如果物品 A 的单位价格（即 \frac{c_i}{w_i} ）大于物品 B，那么一旦物品 A 选择了大于 n 个，设为 x。那么在物品 B 数量足够的情况下，可以在这 x 个物品 A 中，用物品 B 代替一些物品 A。（比如可以拿出去 w_B 个物品 A，拿进来 w_A 个物品 B，这样价值相同，不过花费更少）。也就是说，只有当物品数量小于等于 n 的时候才需要背包，更大可以贪心。所以可以把每个物品取 \min(cnt,n) 个出来跑多重背包，剩下的按照单位价格排序。枚举在背包部分获得的价值，把剩下的花费用来贪心。

         即两个 trick：交换状态，贪心优化。

同余最短路

         有这么一个例题：你有三种物品，每种物品的数量无穷大，每种物品的花费是分别是 x,y,z ，每次询问一个 V，问能否恰好装满 V。 x,y,z\leq 10^5,V\leq 10^{18} 。

         给这种题目归个类：每种物品可以用无限多次，不过每个物品的花费比较小，要判断一个很大的 n 可不可行。

         直接跑背包显然炸掉了，因为容量太太太太太大了。考虑怎么优化，可以发现一旦达到了 k ，那么 k+x,k+2x\cdots 都可以被达到，模式化讲就是说对于大于等于 k 的数 p ，只要 p \equiv k \mod x 那么 p 就可以被达到。那么只要求出对于任意的 q \in [0,x-1] ，最小的可以达到的 k 满足 k\equiv q\mod x 是多少就可以了，因为更大的在 \text{mod x} 同余 q 的数，都可以通过先构成一个 k，再装若干个 x 得到。我们可以把任意的 q \in [0,x-1] 看成一个点，对于一个数 y，就连边 (q,(q+y)~\text{mod}~x,\text{dis}=y) 。最后跑一个最短路，那么到每个点 q 的最短路就是前面提到的 k 。

分层背包

         有这么一个例题：你有一个背包，容量为 V ，你有 n 个物品，花费为 c_i，价值为 w_i，求能获得的最大价值。c_i,w_i,V\leq 2^{30}-1,n\leq 100，c_i 可以分解成 a\times 2^b 的形式且 a\leq 10, b \leq 30 。

         给这种题目归个类：每种物品的花费满足某个特殊条件，要跑一个很大的背包。

         直接跑背包显然炸掉了，因为容量和花费都太太太太太大了。不过可以发现花费都可以分解成一个比较小的数乘上一个 2^k，那么就可以先对这个 k 跑一遍背包，即设 f[i][j] 表示选 j 个 2^i 数的最大价格。然后考虑合并，设 g[i][j] 表示在所有花费小于等于 2^i 的物品中选 j 个 2^i 的方案数（包含两个 2^{i-1} 合并为 2^i 这类）。显然 j 是小于等于 a\times n 的，转移的时候枚举在 2^i 中花费是多少，即 g[i][j]=\max\{f[i][j-k]+g[i-1][k+k+\text{V 的第 (i-1) 位是否为 1}]\} 。

树形背包

总是有出题人喜欢把序列上的题目出到树上，让选手强行处理树上问题。这种行为已经很无趣了。 —— 佚名

有的题目做着做着就上了树。 —— 佚名

树形依赖背包

         有这么一类题目：如果要选择某个物品，那么必须先选择另一个物品，且把所有限制看成连边，最终会形成一个外向树森林，这类即是树形依赖背包。

         树形依赖背包的 DP 状态十分显然：设 f[i][j] 表示 i 子树选择 j 个的最优答案。

         一种较为普通的合并是把一个点的所有子树在该点合并，并且每次枚举到总容量 V，那么总复杂度是 O(n\times V^2) 的。

         这样显然不优，有两种优化。均可以优化到 O(n\times V)

         一种优化是基于 DFS 序的。先把整棵树的 DFS 序拿出来，然后在 DFS 序上 DP，那么就有 f[i][j]=\max(f[i+1][j-c[i]]+w[i],f[i+size[i]-1][j])，即这个点选，那么其子树也可以选，所以就是 i+1，否则其子树不可以选，所以就是 i+size[i]-1 。这种做法因为把树搬到了序列上做，所以无法知道树上的信息（如父亲）。

         一种优化是进入子树的时候，把当前节点的 DP 值赋值下去且强制把它儿子选了，最后遍历一遍出来后，这个子树的 DP 值就是选择了这个儿子的 DP 值，那么还有一种情况就是不选即原 DP 数组，所以最后两个 DP 数组取 \max 即可。

花费为 1 普通树形背包

         有一种人尽皆知的优化卡上界的方法，就是每次只枚举到 size，最后的复杂度是 O(n^2) 的，因为任意一对节点只会在其 LCA 被处理一次。

         但是如果背包容量只有 V，那么如果要卡上界那么就只要枚举到 \min(size,V)，这样子的复杂度是 O(n\times V) 的。（是不是感觉很神奇）

         考虑证明，一种不是那么严谨的证明是，在父亲节点处 \min(size_{fa},V) 的意思是在 fa 子树内选 DFS 序靠后的 V 个，在子节点处 \min(size_{son},V) 的意思是在 son 子树内选 DFS 序靠前的 V 个，那么每个点最多配对 DFS 序比其小或者比其大的 V 个数，所以复杂度是 O(n\times V) 的。

         另一种更为严谨的证明是分四种情况讨论，假设需要合并的是 u,v ：

1. size_u\geq m,size_v\geq m

   一次合并的复杂度为O(m^2)。考虑所有的极小的 size \geq m 的子树（即它里面的所有子树的 size 都小于 m），显然它们两两不相交，所以至多有 \frac{n}{m} 个。此外，这种情况会出现，当且仅当：u 已经合并过的儿子里有极小的子树，并且 v 里面有极小的子树。故而合并的次数为极小的子树个数 - 1。故而这一部分的复杂度是 O(m^2\times \frac{n}{m})=O(n\times m)

2. size_u\geq m,size_v<m

   这种情况的复杂度是 O(m\times size_v)，我们考虑求 \sum size_v 的上界。对于每一个点考虑，它的祖先中，满足 size_x<m 且 size_{fa_x}\geq m 的点至多只有一个，所以会出现这种情况的 (u,v) 至多只有一个，所以 \sum size_v=O(n)，所以这种情况的总复杂度是 O(n\times m)。

3. size_u<m,size_v \geq m

   类似地我们考虑求 \sum size_u 的上界。具体证明同上，故 size_u=O(n)，故复杂度是 O(n\times m)。

4. sz_u<m,size_v<m

   这个时候就是普通的树形背包，对于一整棵大小为 x 的树我们知道这样的复杂度是 O(x^2)。考虑所有的、极大的 size < m 子树（即满足 size_{fa_x} \geq m），每一个这样的子树的复杂度是 O(m^2) ，而这样的子树两两不相交，所以至多有 \frac{n}{m} 个，所以总复杂度为 O(m^2 \times \frac{n}{m})=O(n\times m)。

综上，时间复杂度是 O(n\times m) 。

参考自 这里 。