2024-05-15
经验总结
00

目录

多重背包问题是什么
朴素的优化方法
思考
二进制拆分是什么

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

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

多重背包问题是什么

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

多重背包问题背景:存在容量为 VV 的背包和 NN 组物品,第 ii 组物品有 KiK_i 个且每个价值都为 ViV_i,求背包能装下的物品价值和的最大值。

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

朴素的优化方法

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

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

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

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

思考

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

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

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

二进制拆分是什么

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

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

  1. 20,21,22,...,2k2^0, 2^1, 2^2, ..., 2^k
  2. Z(2k+11)Z-(2^{k+1}-1)

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

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

可以发现,一定不选 PP "物品"时,数量和最大为 2k+112^{k+1}-1。(提一嘴没啥用的,这能很容易地证明这个集合的数量和为 ZZ。)

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

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

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

  1. 让拆分后的"物品"数量和等效地表示选择某个组中的物品数,不会破坏答案空间
  2. 相比朴素的拆分方法,对于有 ZZ 个物品的组,最多只会得到 log2Z+1\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

本文作者:CornWorld

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!