有哪些算法或数据结构是ACM大牛们在比赛中创造出来的？ 第1页

对完全背包问题(unbounded knapsack)的算法。最近投paper查了一些东西，神奇地发现在这个基础问题上ACM界的进展居然领先学术界了。

完全背包问题：给定 种物品，第 种物品的重量为 ，价值为 ，数量无限，从中选出总重不超过 的一些物品使总价值最大化。以下假设 为正整数。

众所周知这个问题有一个 复杂度的动态规划算法。但是我们还可以研究这个问题关于其他参数的复杂度：令 表示单个物品的最大重量，我们想知道有没有算法的复杂度只跟 和 有关，而和 无关，这样我们就可以处理 非常大的情形了。

理论界我能查到的一些进展有：

2009: Arie Tamir[1]利用整数背包和分数背包之间的一些联系，给出了一个复杂度为 的算法。看起来这是第一个给出复杂度为 形式的work。

2018: Bateni et al.[2](STOC)给出了复杂度为 的算法。(话说其实可以简化为 ，因为对于unbounded的情况我们总可以wlog assume ，作者在倒腾自己lemma的过程中还是不够细啊)。其核心思想为利用鸽巢原理得到的以下引理：

Lemma 1. 令 为收益比( )最高的那个物品。那么一定存在一个最优解满足选取的其他物品的重量总和 。

2018: Eisenbrand和Weismantel[3](SODA)利用Steinitz Lemma也证明了以上的Lemma 1。当然这只是他们主要结果的一个小小小推论(他们结果的推论就可以导出Lemma 1的高维情形)。

2019: Axiotis和Tzamos[4](ICALP)给出了一个复杂度为 的算法(更准确的复杂度为 ，这个奇怪的分母是从(min,+)-convolution的一个著名结论那里来的，注意这个分母可以吸收掉分子上的一个 项)。算法的核心思想和下文将要讲到的cf上的那道题是一样的，所以等会再说。这个算法的running time match上了[5]和[6]给出的conditional lower bound(不存在 复杂度的算法)，所以这个问题(终于)就算做完了。

OI/ACM界的成果：

2016: 知乎上 @LightGHLi 的这个回答

给出了Lemma 1的一个证明，注意这个时间就已经比[2,3]早了，并且下方评论区中有知友提示这个思想早有人出过很多遍了。(印象中我初高中的时候见过类似的东西，很像 @wwwwodddd 说的那个，反正当时我是没做出来)。这个算法最早出现的时间还有待考证？大家努力找找或许能比09年还早... 那就能完爆理论界了。

update. 评论区提示这个思想在2006年的Usaco Dec The Fewest Coins一题中就已经出现过了，不过用来解决的问题是knapsack的一个特殊情况coin changing。

2016: codeforces上2016 USP Try-outs的L题考察了完全背包问题在 较小， 很大时的解法。题解中给出了 的做法：(我终于找到题解链接了，可惜是用葡萄牙语写的，所以还是贴个网上搜到的截图吧。这是个巴西的比赛，L题出题人是Arthur Nascimento，题解作者是Yan Soares Couto。)

算法的核心思想是尽量把重量均分成两半然后递归。上图中的 是本文的 ， 是本文的 。结合Lemma 1我们可以wlog assume ，总复杂度为 。这和Axiotis和Tzamos[4]的算法是一样的(在朴素实现(min,+)-convolution的情况下)，且出现时间更早。

尾声：利用我paper的结论可以在 的时间内对所有 求出最优解。算法非常简单，但是正确性分析并不显然，用到了一些数论工具。代码在这里，压到8行之后顺利成为了cf上的最短提交。

References

[1] Tamir A. New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems[J]. Operations Research Letters, 2009, 37(5): 303-306.

[2] Bateni M H, Hajiaghayi M T, Seddighin S, et al. Fast algorithms for knapsack via convolution and prediction[C]//Symposium on the Theory of Computing (STOC). 2018.

[3] Eisenbrand F, Weismantel R. Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma[C]//Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018: 808-816.

[4] Axiotis K, Tzamos C. Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms[C]//46th International Colloquium on Automata, Languages, and Programming (ICALP), 2019.

[5] Cygan M, Mucha M, Wegrzycki K, et al. On Problems Equivalent to (min,+)-Convolution[C]//44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017, 80: 22.

[6] Künnemann M, Paturi R, Schneider S. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming[C]//44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017.