最近没有怎么更新博客，因为一直比较忙。最近发现所里在做的一个项目中，可以抽出一部分内容和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并没有更难，甚至某些时候很可能有多项式算法，这说明推广了，也有可能变简单，特殊情况也有可能更难。但是特殊情况的算法思想可以借鉴用来解决推广了的问题。