0-1背包问题与子集合加总问题的近似算法

最近没有怎么更新博客,因为一直比较忙。最近发现所里在做的一个项目中,可以抽出一部分内容和0-1背包问题、子集合加总问题非常相似(虽然表面上不容易看出相似点),所以看了一些这方面的资料和论文,这里主要对问题特点和算法思想做一些整理。
这类问题其实很有意思,做数学和做计算机的人都会研究,而且我这里将要提到的论文都是做计算机的人所写的。

问题简述
0-1 Knapsack Problem (0-1背包问题,下面简称KP)和Subset Sum Problem (子集合加总问题,下面简称SSP)是经典的NP完全问题。
两个问题简要描述如下:

KP:有$n$个物品要放入背包,第$i$个物品的价值为$c_i$,占据体积为$v_i$,背包的总容积为$V$,要选择一部分物品放入背包,使得他们的总价值最大。对应的优化问题是
$\max_{x_i} \sum c_i * x_i $
$\mbox{s.t.} \sum v_i * x_i \le V, x_i \in \{ 0, 1 \} $
这里$x_i$代表是否选取第$i$个物品进背包,等于$1$就代表放入背包,等于$0$代表不放入背包。

SSP: 给一个集合$\{c_1, c_2, \ldots, c_n \}$,还有一个目标值$V$,问能否选出一个子集,使得子集中元素求和刚好等于$V$。我们一般考虑的是他的另一种表述方式:选出一个子集,使得子集中元素求和不超过$V$,且尽量大。对应的优化问题是
$\max_{x_i} \sum c_i * x_i $
$\mbox{s.t.} \sum c_i * x_i \le V, x_i \in \{ 0, 1 \} $
这里$x_i$代表是否选入子集,等于$1$就是选入子集,等于$0$就是不选入子集。

SSP是KP的特殊情况,也即当$c_i = v_i$的时候,KP退化为SSP,从问题式子上看,也完全一样了。
尽管如此,研究了KP不代表就不用研究SSP了,后面会说明这一点。

精确算法与近似算法
这两个问题都有很简单的动态规划算法可以精确求解,但可惜算法的时间复杂度是伪多项式的,也即和$V$相关,但$V$不是问题输入数据的规模,$n$才是。在ACM竞赛等算法比赛中,经常会遇到一些问题属于KP的变种,而伪多项式算法也就足够了。由于网上资料很多,而且难度不大,这里就不详细介绍了。如果你不知道,请你搜索“动态规划求解0-1背包问题”。
这里我们更关心多项式近似算法,也即PTAS(Polynomial Time Approximation Scheme),也即对任意给定的$\epsilon$,算法可以在关于$n$的多项式时间内求得一个解,且该解和真实最优解的最多相差$\epsilon$倍。
实际上这两个问题都有FPTAS(Fully PTAS)算法,也即时间复杂度不仅要是$n$的多项式,而且还要是$\frac{1}{\epsilon}$的多项式。

KP的近似算法
KP有非常简单的近似算法。
对任意$\epsilon$,令$P = \max_i c_i$,$K = \frac{\epsilon * P } { n}$,记$c_i’ = \lfloor \frac{c_i}{K} \rfloor$ (这里$\lfloor \cdot \rfloor$表示向下取整)
则使用$c_i’$代替$c_i$求0-1背包问题,求得的$x$即为$\epsilon$近似解。这是因为每一个物品由于取整而产生的误差都很小。
而这时候,由于$c_i’$都是整数,可以使用动态规划算法求解,容易算得动态规划的状态数至多$n \lfloor \frac{ P}{K} \rfloor$个,因此整个算法的时间复杂度为$\mbox{O}(n^2\lfloor \frac{ P}{K} \rfloor) = O(n^2 \lfloor \frac{n}{\epsilon} \rfloor ) $,
算法复杂度之所以能够达到多项式,是由于取整减小了动态规划的状态数,而$K$的出现是为了控制因取整而产生的误差,$K$足够小的时候就能保证解的相对误差不会超过$\epsilon$
此算法参考 Vijay V. Vazirani写的书 Approximation Algorithms(点击下载) , 第8.1,8.2章节(第69页-70页)
虽然这不一定是最快的多项式近似算法,但暂时没看到别的算法在任何情况下复杂度都能更低。
我自己也没有想到更好的。而有趣的是我最近在思考另一个等价的问题,但在发现等价性之前,我也想出了一个思路几乎相同,复杂度完全一致的算法。现在看来,其实本质是同一个算法。

SSP的近似算法
根据前面所述,SSP是KP的特殊情况。所以KP的近似算法就可以认为是SSP的近似算法了。但是,之所以单独考虑SSP,是因为他可以求得更快。
SSP也有思路非常类似的算法,可以在一些国外的教学资料上看到。如这一篇(点击下载)。但是时间复杂度都比较高,事实上,SSP有$\mbox{O}(\min \{ \frac{n}{\epsilon} , n + \frac{1}{\epsilon^2} \log(\frac{1}{\epsilon}) \} )$的算法。我认为这个结论是比较漂亮的,复杂度严格比上面提到的KP的算法要低,而且低很多。
为了说明算法思想,我们先再深入理解一下前面的算法。
前面的算法是用取整来控制复杂度,取整的本质事实上是将状态空间划分成若干段,每一段只取一个端点作为“代表”,这样状态数就会是多项式的,总的算法复杂度也就是多项式的。在SSP中,我们可以不事先取整,但仍然将状态空间分段,让每个段记录两个数值(也即选两个“代表”),一个是落在该段上的最小子集和(最小代表),一个是落在该段上的最大子集和(最大代表)。这样我们的状态数相当于比前面KP的算法多了一倍,而且是需要动态维护的,但是由于误差控制的更好(极端的例子是如果集合只有一个数,这么做就没有误差),没有取整那么大的误差,所以不需要分那么多段就能保证解的相对误差不超过$\epsilon$,因此最终算法复杂度会低。
此算法参考 Hans Kellerer等人的论文 An efficient fully polynomial approximation scheme for the Subset-Sum Problem (点击查看) Journal of Computer and System Sciences 66 (2003) 349–370
可以发现,这个算法是不能简单推广到0-1背包问题上的。

SSP的拓展问题——ISSP
Anshul Kothari等人在2005年研究Uniform-Price Auction Clearing(其实我也不知道这是啥问题)的论文中提出了Interval Subset Sum Problem (下面简称ISSP),他是SSP的一个推广。这个问题没有前面的问题这么有名(事实上我没看到第二篇论文讨论这个问题),但刚好我也发现了另外一个实际问题可以抽象成这个模型,所以我觉得还是很有意义的。问题简要描述如下:
给定$n$个区间$[a_i,b_i]$,对每个区间可以选择上面的一个数,也可以什么都不选,使这些数的和不超过目标值$V$,且尽量接近。对应的优化问题是
$\max_{x_i,y_i} \sum y_i * x_i $
$\mbox{s.t.} \sum y_i * x_i \le V, x_i \in \{ 0, 1 \}, y_i \in [a_i, b_i] $
至少从形式上看,他不再是线性的了,而且当$a_i=b_i$时退化为SSP。所以似乎更难了。
实际上这个问题也能改写为线性模型。
$\max_{x_i,y_i} \sum y_i $
$\mbox{s.t.} \sum y_i \le V, x_i \in \{ 0, 1 \}, y_i \in [x_i * a_i, x_i * b_i] $
从直观上看,如果$a_i$很小,$b_i – a_i$很大,这个问题似乎很容易解。我已经可以给出看上去不是太强的条件,在该条件下,ISSP是多项式可解的,具体这里就不给出了。但无论如何,In general,ISSP也是NP难问题。
Anshul Kothari等人的论文中也给出了一个FPTAS算法,比较有趣的是,这个算法和上面的SSP的算法思想是一致的,时间复杂度也是一致的。因此这一算法应当是受到上面所述的SSP的算法启发而设计的,而且是一个比较简单的推广。
此ISSP算法参考论文为 Interval Subset Sum and Uniform-Price Auction Clearing (点击查看) Computing and Combinatorics, Lecture Notes in Computer Science Volume 3595, 2005, pp 608-620

一些启示
1,SSP是KP的一个特殊情况,但是他们的近似算法复杂度却可以完全不同,这说明特殊问题可以有特殊算法。使用General的算法是可以的,但需要仔细想想问题是否有特殊的地方没发现,是否有更具针对性的算法没找到。
2,ISSP是SSP的一个推广,也即SSP是ISSP的特殊情况。但事实上ISSP并没有更难,甚至某些时候很可能有多项式算法,这说明推广了,也有可能变简单,特殊情况也有可能更难。但是特殊情况的算法思想可以借鉴用来解决推广了的问题。