Subset Sum 问题单个物品重量限制前提下的更优算法

前言

看了 ShanLunjiaJian 关于这个问题的文章，是完全没看懂，沙东队爷的中枢神经内核配置把我偏序了。叉姐在下面提了个论文，论文找不到资源，谁搞到了可以 Q 我一份之类的拜谢了。然后找到了这个可能是阅读笔记或者是翻译的的东西，这下算是看懂了。

感觉还是很有意思，对于 DP 的状态设计、优化思路等都有很大启发，所以写一下。

（有单个物品重量限制的）Subset Sum 问题

ShanLunjiaJian 把这个叫做 Knapsack，我是要批判的，因为感觉上是带不了权的啊，这不是Knapsack！

那么描述一下这个问题：给定 $n$ 个物品，每个物品有一个正整数重量 $w_i$，保证 $1\le w_i\le V$，其中 $V$ 是所谓的重量限制。现在给一个容量 $C$，取这些物品的一个子集，使得重量和不能超过这个容量，然后要求物品总重量的最大值，也就是让浪费的容量最小。

低论

这个问题显然有一个做法，叫做把它当作一个普通 Knapsack 问题，时间复杂度 $\mathrm{\Theta }(nC)$。那么有意义的 $C\le nV$。所以其实上界是 $n^{2}V$。现在我们有高论！可以做到 $\mathrm{\Theta }(nV)$。

高论

首先这个问题有一个经典贪心做法，叫做给所有元素从小到大排个序，然后选一个前缀使得再多选一个就会超过容量限制。这个做法当然是错的，但是可以基于它给出的这个既有选择方法去做调整，那么这样一来，剩余容量就是 $\mathrm{O}(V)$ 的（如果大于 $V$ 就一定可以再多选一个，矛盾了），很可做！

现在我们面临的问题是什么呢？我们的 DP 可能出现负数重量了（因为要支持取消选择一些原本选了的物品），这种条件下，要去维持我的剩余容量始终保持 $\mathrm{O}(V)$，是有一点难度的。怎么办呢？

考虑一个直觉，是不是可以这样去操作：当试图去取消一个原先选的物品（也就是选负数）的时候，一定要让当前容量是超额的；当去选正数的时候，一定要让当前容量是不满的。考虑最优解是不是一定能用这种方式构造出来——显然是可以的。证明可以这样想，假设我从贪心生成的“基础解”开始，按照某个顺序去把它修正成最优解，是不是每一步都一定能按照上述规则操作。那么可以这样想：如果现在容量是超额的，但是不存在某个元素使得“最优解中没选它，当前解中选了它”，那么最优解选择的集合一定包含当前解，它的容量就一定也是超额的，矛盾，所以一定有办法去进行操作。反之亦然，因此按照这样的规则操作，必然能得到某种最优解。更棒的是，在这样操作的过程中，剩余容量始终在 $[-V,V]$ 以内！真是好极了，接下来只需要基于这种构造方案来 DP 就可以了。

先设计一个朴素 DP。设贪心得到的分界点为 $p$，使得目前选择的集合是标号 $\le p$ 的物品，$S_0=\sum _{i=1}^p{w}_i$。那么设 $g_{i,j,k}$ 表示右边决策到 $i$，左边决策到 $j$，当前剩余容量为 $k\in [-V,V]$ 的方案是否存在。这个 DP 复杂度是 $\mathrm{\Theta }(n^{2}V)$，真是一点优化效果都没有！但是这个东西的进一步改造非常方便，这就是下一步的想法。

注意到这是一个值为 Boolean 类型的 DP，如果发现某一维具有单调性，那么就可以压缩掉这维。可以观察到：如果 $g_{i,j,k}=1$，那么对于任何 $t\le j$，都有 $g_{i,t,k}=1$——毕竟在左侧做出更多决策一定不会使可达集合变小。那么可以设 $f_{i,k}=max\{0\le j\le p|g_{i,j,k}=1\}$。如果不存在这样的 $j$，设为 $-1$。那么 DP 的初始条件是 $f_{p+1,S_0}=p$。转移如下：

$$\{\begin{array}{lll}{f}_{i+1,k+w_i}\leftarrow f_{i,k},& k\le 0& (1)\\ f_{i+1,k}\leftarrow f_{i,k},& \text{any}& (2)\\ f_{i,k-w_t}\leftarrow t-1;& k\ge 0\wedge t\le f_{i,k}& (3)\end{array}$$

整体按照 $i$ 递增转移，每个 $i$ 按照 $k$ 递减的方向做转移 (3) 即可。时间复杂度是 $\mathrm{\Theta }(n^{2}V)$，真是一点优化效果都没有！但是这个 DP 已经是 2D-1D 的了，进一步改造非常方便，这就是下一步的想法。

注意到只有转移 (3) 的复杂度不对，而这个转移很大程度上是重复的——某些转移过程，在 $i=a$ 可以做，在 $i=a-1$ 同样可以做。那么可以尝试去掉这些转移，让本质相同的转移在最小的可以进行的 $i$ 处去进行。注意到对于某个特定的 $k$，关于某个特定的 $t$ 的转移能否进行，只和 $f_{i,k}$ 是否足够大有关，而我们有单调性 $f_{i,k}\le f_{i+1,k}$，这是因为转移 (2) 的存在。所以转移 (3) 的条件可以改为 $k\ge 0\wedge f_{i-1,k}\le t\le f_{i,k}$。这样一来，某个特定 $k$ 对总复杂度的贡献是 $\mathrm{O}(n)$ 的，所以总复杂度就变成了 $\mathrm{\Theta }(nV)$！我们成功了！

后记

有人问有什么应用？我不知道啊。这么基础的东西一定有很多应用前景吧！（心虚）