关于一类背包问题的常见 trick

· · 算法·理论

因为忘了这个 trick 而在模拟赛被套路题薄纱两次，特此总结一下。

模板

对于一个共有若干类物品的无限背包模型，若第 i 类物品的体积恰好为 i，或者第 1 类物品体积固定、所有类物品体积呈等差数列递增，从中取 k 个物品，求装满容量为 n 的背包的方案数。

解法

设 f_{i,j} 表示前 i 个物品，总体积为 j 的总方案数。显然 f_{0,0}=1。

假设我们已经得到了当前状态所对应的物品集合，记为 S。为转移到新的状态，可以对其进行两种操作：

  1. 加入一个新的初始体积的物品。即若体积最小的一类物品体积为 x，将 x 加入 S。

  2. 将所有物品体积加上某个数，使集合里每个物品成为其所属的类的下一类物品。即设体积数列的公差为 d，对于所有 x \in S，令 x \leftarrow x + d。

由此可得到转移方程为 f_{i,j} = f_{i-1,j-x} + f_{i,j-i \times d}，复杂度 \mathcal O(nk)。

一些例题

目前只做到了两道，以后做到再添加（

LOJ #6089. 小 Y 的背包计数问题

考虑根号分治，体积 \le \sqrt{n} 的物品直接跑多重背包即可。注意对于第 i 类物品，模 i 同余的体积可以利用前缀和优化转移。这部分复杂度是 \mathcal O(n \sqrt{n})。

对于体积 > \sqrt{n} 的物品，注意到这样的物品一共至多取 \sqrt{n} 件，使用类似上述 trick 转移即可。最终转移方程为 f_{i,j} = f_{i-1,j-(\sqrt{n}+1)} + f_{i,j-i}，这部分复杂度也是 \mathcal O(n \sqrt{n}) 的。

合并两个 DP 结果即可用 \mathcal O(n \sqrt{n}) 的复杂度通过本题。

sequence

由于是某校校内 OJ 模拟赛的题就不放链接了（

题目大意：求长度为 k、所有元素之和为 n 的不降正整数数列 的个数，数据范围：n \le 10^5, k \le 10^4。

利用上述思想不难发现，构造数列的方法如下：

  1. 在数列开头添一个 "1"

  2. 将所有元素整体 +1

设 f_{i,j} 表示 当前长度为 i，各元素之和为 j 的总方案数。

转移：f_{i,j} = f_{i-1,j-1} + f_{i,j-i}。

时间复杂度 \mathcal O(nk)，通过 压维/滚动数组 可以做到 \mathcal O(n) 的空间复杂度。

其实这个方法本质和背包是等价的，原问题可以转化为：（以下文字来自官方题解）

有重量为 1,2,3,\cdots 的物品各无数件，从中选恰好 k 件，使其恰好装满大小为 n 的背包，求方案数。