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

多重背包问题是什么

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

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

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

朴素的优化方法

可以看到，多重背包化为 01 背包最简单的方法就是把“组”的概念拆掉，把问题化为：存在容量为 $V$ 的背包和 $\sum_{i=1}^{N}C_i$ 个"物品"，每个"物品"等效于某组物品中的一个物品（不知道怎么严谨的表示价值来着 XD） 那这样的话，可见的是复杂度爆炸，且显然存在子问题重复（多个"物品"的价值相同）。

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

思考

反过来观察上面的操作，其正确性是显而易见的：上述的拆分操作不会影响到答案。即原先需要选择某个组中的 $X$ 个物品，在拆分后也会进行这样的选择（选择等效的 $X$ 个"物品"）。而使用某些奇怪的拆分操作，比如二分拆分什么的，很容易增加限制（比如对于某个组，拆分后的"物品"凑不出来正解中选择的物品数量），从而得不到正解。 在这里可以看出一些端倪：如果我们对任意组（假设有 $Y$ 个物品）进行拆分，得到的"物品"们的数量可以凑出来任意 $[0, Y]$，那是不是不会增加限制呢？

二进制拆分是什么

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

这里就可以尝试用 CS 中常用的二进制拆分操作，即对于某组中的 $Z$ 个物品，我们拆成下面的"物品"集合（下面是不太严谨的表述，意会即可） $NC=\set{2^0, 2^1, 2^2, ..., 2^k, Z-(2^{k+1}-1)}$ 在这个集合中，只有 $Z-(2^{k+1}-1)$ 项是比较特殊的，为了方便，在后面称呼 ta 为 $Z'$；因为这个值的意义是某个"物品"的数量，后面会使用 $Z'$ "物品"来代指"物品"的数量为 $Z'$ 的"物品"。 接下来就应该尝试证明这种拆分能表示的答案区间了。在这里进行分类讨论，分别是一定不选 $Z'$ "物品"的情况和一定选 $Z'$ "物品" 的情况。

可以发现，除去 $Z'$ "物品"后的数量和为 $2^{k+1}-1$。（提一嘴没啥用的，这能很容易地证明这个集合的数量和为 $Z$。） 在理解下面这一句的时候，请放弃十进制的思考方式！使用代数的方法思考！！ 在一定不选 $Z'$ "物品"时，根据进制转换相关的常识，剩下的"物品"的数量的子集的和 $S\in[0, 2^{k+1}-1]$。 在一定选 $Z'$ 物品时，同理，其子集的和 $S'\in[Z-(2^{k+1}-1), Z]$。 我们可以很显然的发现，在这里 $S$ 和 $S'$ 可以覆盖整个区间，即 $S\cap S'=[1, Z]$ 而在 01 背包问题中，选择是任意的，所以这两个子问题完全可以合并，得到完整的答案区间（和倍增 ST 表的子问题合并比较接近）。

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

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

TODO: 写一下代码