#dp #背包dp #多重背包 #算法优化 #经验总结

看到多重背包 -> 01 背包的转化操作中，使用了二进制拆分。第一眼觉得这种方法的正确性很难判断，就想了个把小时，总算是想明白了，写篇文纪念一下。

多重背包问题是什么

为了防止误会，在原问题中的物品不加引号，在转换后的问题中的物品加引号

多重背包问题背景：存在容量为 $V$ 的背包和 $N$ 组物品，第 $i$ 组物品有 $K_i$ 个且每个价值都为 $V_i$，求背包能装下的物品价值和的最大值。

TODO: 使用二维 dp 写一下思路

朴素的优化方法

为了更好地表达，下面使用 "物品"的数量 来表示拆分后的"物品"于原问题中的等效数量

我们可以发现多重背包问题并没有这么多限制，即可以尝试把问题转化为 01 背包问题。
最简单最朴素的方法就是把"组"的概念拆掉：把「每种物品选 $k_i$ 次」等价转换为「有 $k_i$ 个相同的物品，每个物品选一次」¹。
那这样的话，可见的是复杂度爆炸（时间复杂度为 $O(V \sum_{i=1}^n K_i)$），且显然存在子问题重复（多个"物品"的价值相同）。

显然，复杂度中的 $O(nV)$ 部分无法再优化了，我们只能从 $O(\sum K_i)$ 处入手。为了表述方便，我们用 $A_{i,j}$ 代表第 $i$ 种物品拆分出的第 $j$ 个物品。²
在朴素的做法中，$\forall j\leq K_i$，$A_{i,j}$ 均表示相同物品。而效率低的原因在于我们在后续跑 01 背包时进行了大量重复性的工作。
举个栗子，这个算法实际上考虑了「同时选 $A_{i,1},A_{i,2}$」与「同时选 $A_{i,2},A_{i,3}$」这两个完全等效的情况。那么优化拆分方式就成为了解决问题的突破口。³

TODO: 使用 01 背包写一下朴素优化的代码

思考

观察上面的操作，其正确性是显而易见的：上述的拆分操作不会影响到答案。即原先需要选择某个组中的 $X$ 个物品，在拆分后也会进行这样的选择（选择等效的 $X$ 个"物品"）。

那么什么情况下会没有正确性呢？
举个栗子，假设我们使用了某些奇怪的拆分操作，把某个有 $4$ 个物品（在朴素的做法中，这个组会被划分成 ${1, 1, 1, 1}$）的组划分成了 $\{2, 2\}$ 个物品的形式，而正解会选择这个组的 $3$ 个物品。显然，这种划分方式无论如何也没办法凑出来 $3$ 这个数字，而朴素的做法可以（$1+1+1=3$）。

根据上面的例子，可以发现错误的划分方法会增加限制（比如对于某个组，拆分后的"物品"凑不出来正解中选择的物品数量），从而得不到正解。
在这里可以看出一些端倪：如果我们对任意组（假设有 $Y$ 个物品）进行拆分，得到的"物品"们的数量可以凑出来任意 $[0, Y]$，那是不是不会增加限制呢？

二进制拆分是什么

这里就可以尝试用 CS 中常用的二进制拆分操作，即对于某组中的 $Z$ 个物品，我们拆成下面的"物品"集合（下面是不太严谨的表述，意会即可）
$NewC=\set{2^0, 2^1, 2^2, ..., 2^k, Z-(2^{k+1}-1)}, k\in \mathbb{N}, Z<2^{k+1}$

注意，上面提到的集合 $NewC$ 是我们构造的有特殊性质的集合。
为什么要这么构造呢？我们可以简单看一下构造，可以简单地分为两部分：

1. $2^0, 2^1, 2^2, ..., 2^k$
2. $Z-(2^{k+1}-1)$

可以发现，只有 $Z-(2^{k+1}-1)$ 项是比较特殊的，为了方便，在后面称呼 ta 为 $P$。
因为这个值的意义是某个"物品"的数量，后面会使用 $P$ "物品"来代指"物品"的数量为 $P$ 的"物品"。

接下来就应该尝试证明这种拆分能表示的答案区间了。在这里进行分类讨论，分别是 一定不选 $P$ "物品"的情况 和 一定选 $P$ "物品" 的情况。

可以发现，一定不选 $P$ "物品"时，数量和最大为 $2^{k+1}-1$。（提一嘴没啥用的，这能很容易地证明这个集合的数量和为 $Z$。）

在理解下面这一句的时候，请使用组合排列与代数的方法思考！
在一定不选 $P$ "物品"时，剩下的"物品"的数量的子集的和 $S\in[0, 2^{k+1}-1]$。
在一定选 $P$ "物品"时，其子集的和 $S'\in[Z-(2^{k+1}-1), Z]$。

在这里，因为 $Z<2^{k+1}$，我们可以证明 $Z-(2^{k+1}-1) \leq 2^{k+1}-1$
所以，在这里 $S$ 和 $S'$ 的并集可以覆盖整个区间，即 $S\cap S'=[1, Z]$
而在 01 背包问题中，子问题是可重复贡献问题，所以这两个子问题完全可以合并，得到完整的答案区间（和倍增 ST 表的子问题合并的可行性证明比较接近）。

总结一下，使用这种方法，我们可以做到：

1. 让拆分后的"物品"数量和等效地表示选择某个组中的物品数，不会破坏答案空间
2. 相比朴素的拆分方法，对于有 $Z$ 个物品的组，最多只会得到 $\lfloor \log_2{Z} \rfloor+1$ 个"物品"，优化效果理应不错

TODO: 写一下代码

Footnotes

1. 此句述来自 OI-Wiki (OI-wiki/docs/dp/knapsack.md at master · OI-wiki/OI-wiki (github.com)) ↩

2. 此段描述改写自 OI-Wiki ↩

3. 此段描述改写自 OI-Wiki ↩