关于01背包优化问题中论文和竞赛做法的不同之处
在给USACO Platinum出模拟赛的时候, 我设计了如下的压轴题:
有一个容量为 \(V\) 的背包, 有 \(n\) 种物品, 占用的空间为 \(c_i\) , 权值为 \(v_i\) - 其中权值不可重集合 \(v\) 元素个数小于 \(C\). 每个物品可以可以选择拿或者不拿, 求物品权值的最大值是多少?
简单来说, 就是01背包, 但权值的集合很小. 经典做法的时间复杂度是 \(O(nV)\).
我得到了错误的做法, 在分别求助了 w33z 和 wlzhouzhuan 后, 我得到了两种完全不同的做法, 分别是经典的论文做法和竞赛做法. 这其中的区别和相似之处令我非常感兴趣, 故写下进行记录.
这道题尽然存在如此 “初等” 的做法, 通过以另一种方式巧妙的利用单调性, 绕过了 (max, +) 卷积的困难性
可能这就是算法竞赛的魅力吧, 固然我仰慕这些研究者的工作, 也深知在不远的将来我可能也会成为其中之一
或者默默无闻, 没有任何有意义的成就, 或者完全没有能力研究高深的问题, 但在掌握着这算法竞赛中有限的工具库中, 往往也可以解决困难的问题
所为 “分治优化抉择单调性” 初见是可能感到疑惑, 为学习这种技巧性极强的做法感到不快, 但这其实不妨是选手们做出的一次又一次的尝试:
在没有足够的数学的工具的情况下依然解决了一个又一个的难题, 哪怕做法没有那么的完美
但却足够震撼, 能利用这一套更为简朴的工具, 巧妙的克服一个个困难, 得到一个哪怕不那么完美的答案
这也许就是算法竞赛的艺术吧: 我的水平不足以理解竞赛中比较前沿的研究, 但是能看到自己所了解的算法在别人的使用下解决一个又一个困难的问题时, 我找到了我所努力的意义.
在进入主题前, 我先对这问题进行一些简单的分析以助于理解.
在这个问题当中, 可以发现权值和空间的意义是可以互换的, 因此可以选择一个简单的情景进行解决.
我认为比较简单的情景是令空间的集合有限的情况, 同时考虑一些有序数列, 代表 \(c_i\) 这个占用空间的物品当中所有的权值. 这个问题存在单调性, 如果对于 空间为 \(c_i\) 的物品选择 \(x\) 个, 那肯定是价值最大的一些.
对于每一个 \(c_i\) 维护一个函数 \(f_i(t)\), 代表对于空间为 \(c_i\) 的物品中我花费 \(t\) 的空间所能得到的权值的最大值. 那么这个问题就转化成了求解 \(f_i(t)\) 的 (max,+) 卷积和.
发现 \(f_i(t)\) 是类似于跳跃步数为 \(c_i\) 的函数同时在这些位置单调的, 之后称此函数为 \(c_i\) step monotonic function.
我的错误思路如下:
lemma 1.1: 对于凸函数 f(x), g(x), \(x \in X\) 其 (max,+) 卷积可以 \(O(|X|)\) 求出.
利用闵可夫斯基和去求解凸函数的 (max,+) 卷积, 显然 \(f_i(t)\) 函数在离散化之后是单调的, 所以考虑对离散化后的 \(f_i(t)\) 进行经典算法: 差分后归并排序, 然后考虑对离散化前函数的映射关系.
可以注意到进行了 (max,+) 卷积后的函数的每一个元素对应到原结果当中连续的一段, 可以考虑维护这一段的左端点和右端点来解决.
lemma 1.1: 对于凸函数 f(x), k step monotonic function g(x), \(x \in X\) 其 (max,+) 卷积可以 \(O(|X|)\) 求出.
如果算法成立, 时间复杂度是 \(O(DV)\) 的, 但是算法是错误的, 因为无法 (max,+) 卷积后的函数并不保证凸性.
在论文当中 arXiv:1802.06440v2 (Kyriakos Axiotis, MIT, Christos Tzamos, University of Wisconsin-Madison), 作者解决了这个问题.
利用 Monge 矩阵的特殊性质, lemma 1.1 和 lemma 1.2 可以分别加强为:
lemma 1.3: 对于任意函数 f(x), 凸函数 g(x), \(x \in X\) 其 (max,+) 卷积可以 \(O(|X|)\) 求出.
lemma 1.4: 对于任意函数 f(x), k step monotonic function 函数 g(x), \(x \in X\) 其 (max,+) 卷积可以 \(O(|X|)\) 求出.
故问题得到解决, 时间复杂度为 \(O(DV)\), 证明略.
这个算法的专业性质过强, 并且要求读者有一定的大数的理解. 导致我花了很久也没有理解.
我找到了在算法竞赛中对应题目: LOJ6039. 我记得曾经做这道题的时候我的想法是部分DP整体贪心 - 正解对于我来说过于复杂, 我就没有尝试理解.
在询问 wlzhouzhuan 这道题后, 他给出了一个巧妙的OI做法:
进行动态规划, 发现自然满足抉择单调性, 因此考虑cdq分治优化动态规划, \(O(DV\log V)\).
一个及其复杂的问题就被这样巧妙的以一个 log 的代价轻松的解决了.