子集和问题的完全多项式近似方案
２０１2年 2月
一、 作业背景：
1、 子集和问题简介
子集和问题的一个实例是一个对(S,t),其中S 是一个正整数的集合{x 1, x 2, x 3,..., x n },t 为一个正整数。这个判定问题是判定是否存在S 的一个子集，使得其中的数加起来恰为目标值t 。这个问题是NP 完全的。
与此判定问题相联系的最优化问题常常出现于实际应用中。在这种最优化问题中，希望找到
｛x1,x2……xn ｝的一个子集，是其中元素相加之和尽可能地大，但不能大于t 。例如, 假设我们有一辆能装不多于t 磅重的货的卡车，并有n 个不同的盒子要装运，其中第i 个的重量为xi 磅。要在不超过重量极限的前提下，将货尽可能的装满卡车。
2、 开发平台
Eclipse + Jdk 1.7
二、 问题分析：
子集和问题实际上是背包问题的特例, 就是背包问题中项的值和他们的大小相同。课本上给的算法实质就是个动态规划的方法。按照它给的伪代码实现之后，可以得出一个精确解。后来参考了算法导论书中对子集和采取的完全多项式时间近似方案来进行处理。
（一），给出一个指数时间的准确算法
假设对S 的每个子集S ’，都计算出S ’中所有元素的和。接着，在所有元素和不超过t 的子集中选择 其和最接近t 的那个子集。显然，这一算法将返回最优解。但它可能需要指数级的时间。为了实现这个算法，可以采用一个迭代过程：第i 轮迭代中，计算L +x 的所有子集的元素和，计算的基础是{x 1, x 2, x 3,..., x i -1}的所有子集和。在此计算过程中，一旦某个特定的子集S ’的和超过了t, 就没有必要再对它进行处理了，因为S ’的超集都不会成为最优解。下面给出这一策略的一个实现。
EXACT-SUBSET-SUM 的输入为一个集合S={x 1, x 2, x 3,..., x n }和一个目标值t ；这个过程以迭代的方式计算列表L i , 其中列出了{x 1, x 2, x 3,..., x i }的所有子集的和，这些和值都不超过目标值t 。接着，它返回L n 中的最大值。
如果L 是一个由正整数所构成的表，x 是一个正整数，我们用L +x 来表示通过对2中每个元素增i
2，3，5，9}，则L+2=｛3，4，5，7，11｝加x 而导出的整数列表。例如, 如果L ={1，。我们也对集合应用这
个记号，因而 S +x ={s +x :x ∈S }
我们还用到一个辅助过程MERGE-LISTS （L ，L ’），返回对它的两个已排序的输入列表L 和L ’合并及删除重复值后所产生的排序列表。
EXACT-SUBSET-SUM （S,t ）
1 n ← |S|
2 L0←
3 for I ← 1 to n
do L i ←MERGE-LIST(L i -1, L i +x )
remove from L i every element that is greater than t
return the largest element in L n
即P =P i -1 P i +x i , 可以通过对i 的归纳来证明，表L i 是一个包含P i 中所有值不大于t 的元素有序表。因为L i 的长度可大至2，一般来说EXACT-SUBSET-SUM 是一个指数时间的算法。
（二），完全多项式时间近似方案
对子集和问题我们可以导出一个完全多项式近似方案，在每个列表上L i 被创建后，对它进行”修整”，具体思想是如果其中有两个值比较接近，那么处于寻找近似解的目的，没有必要同时保存这两个数。更准确的说，我们采用一个修正参数δ，满足0
y ≤z ≤y (1+δ)
可以将这样一个z 看成是新表L ' 中代表y 的。每个y 都有一个满足不等式的z 的替换。如：
L ={10,11,12,15,20,21,22,23,24,29}
则可以休整L 而得
L ' ={10,12,15,20,23,29}
其中被删除的值11由10来代表，被删除的值21和22由20代表，被删除的值24由23代表。表的休整版本中的元素也是原表的元素，对一个表加以休整后，可以大大减少表中的元素，同时还可以在表中为每个人被从该表中删除的元素保留一个与其很接近的且略小一些的代表值。
在给定L 和δ的情况下，在时间O(m)内休整一个输入表L =,
假定L 已经排成单调递增序。该过程的输入是一个休整过的有序表。
TRIM （L ，δ）｛
1 m←|L |
2 L ’ ←
3 last←y 1
4 for i←2 to m
5 do if y i >last.(1+δ)
6 Then append y i onto the end of L ’
7 last←y i
Return L ’
｝
L 的元素被按照单调递增次序加以扫描，而一个数被加入返回的列表L ’中，仅当它是L 的第一个元素，或者如果它不能由最近被放入L ’的数来代表。
给定过程TRIM 后，可以如下构造近似方案。这个过程的输入为包含n 个整数的集合S={x 1, x 2, x 3,..., x n }（以任意次序放置），一个目标整数t,. 以及一个“近似参数”ε，此处：它返回一个值z ，该值落在最优解的 1+ε倍内。
APPROX-SUBSET-SUM （S, t, ∈）
1. n ←|S|
2. L 0←
3. for i ← to n
4. do L i ←MERGE-LISTS(L i -1，L i -1+x i )
5. L i ←TRIM(L i , ∈/2n )
6. Remove from L i every element that is greater than t
7. let z be the largest value in L n
8. return z
第2行将表L 0初始化为仅包含元素0的一个表。第3~ 6行间for 循环的效果是:将L i 作为
一个包含集合P i 的适当休整版本（去掉大于t 的元素）来计算. 因为L i 是从L i -1构造出来的，故必须保证重复的休整不会引入太多的不准确性。
例子如下:
S={104,102,201,101}
且t=308，ε=0.40.修整参数δ为 ε/8=0.05。、APPROX-SUBSET-SUM 在所指示的各行上计算出如下值: 第2行：L 0=
第4行: L 1=
第5行：L 1=
第6行：L 1=
第4行：L 2=
**
第5行：L 2=
第6行：L 2=
第4行：L 3=
第5行：L 3=
第6行：L 3=
第4行：L 4=
第5行：L 4=
第6行：L 4=
该返回值
z *=302作为答案。由于数据很短，所以我们可以看出最优答案为:307=104+102+101，而302是在 =40%内的。实际上，是在其 2% 之内。
关于APPROX-SUBSET-SUM 是关于子集和问题的一个完全多项式时间近似方案的证明，参见《算法导论》 第864页定理35.8。
（三），相关研究
为了做比较分析，在能求出准确解答的情况下，我们还用回溯法写了求精确解的方法。虽然能得出全部解答，但是如果子集项数稍微多一点基本上就得不出答案了。。。
代码如下：
public class SumOfSub {
private int w []; //用来存放子集 private int m ; //用来存放子集和t
private int x []; //用来判断该子集是否能用来构成目标子集和
public SumOfSub(int w[], int m, int n){ this . w = w; this . m = m; this . x = new int [n]; } public void computeSumOfSub(int s, int k, int r){ x [k] = 1; if (s+w [k] == m ){ printResult(k); } else if (s+w [k]+w [k+1]
//仍有别的可能可以继续求出别的方案, 不要当前的w[k]还有没有别的可能, 前提是已经排好序了
if (s+r-w [k]>=m && s+w [k+1]
}
效果如图：
x [k] = 0; computeSumOfSub(s, k+1, r-w [k]); } } public void printResult(int k){ for (int i=0; i
用动态规划的方案来解决这个问题代码如下：
Public class DP{
int [][] v={{0,0}};//用来放v[i][j]从x0到xi 中选出能组成j 的最优组合，这里是尽可能接近j
int left = t;// 将目标子集和大小付给剩下来要达到的大小 for (int i = 1; i left) { System. out .print("****"); v[i][j] = v[i - 1][j]; } else { // 如果当前的项与从前i-1项选出达到j-1的最优组合的和比v[i-1][j]的大 if (s[i] + v[i - 1][j - 1] > v[i - 1][j]) { v[i][j] = v[i - 1][j - 1]+s[i]; left -= s[i]; } else {
} } } } } } v[i][j] = v[i - 1][j]; System. out .println(" 动态规划" ); int j=t; int [] inOrout={}; for (int i=0;i
由于在java 中数组下表一直报错，在c++中修改代码之后得出效果如下：
三、 算法设计与实现：
核心代码如下：
Vector andSort(Vector s,int x,double e,int t){
//添加新元素到表中 int n=s.size(); for (int i=0;i vs=new Vector(); for (int index=0;index(1+e)*(vs.get(vs.size()-1)) && s.get(index)=0 && s.get(j)>temp){ } s.remove(j+1); s.add(j+1, temp); //s.add(j+1, s.get(j)); s.remove(j+1); s.add(j+1,s.get(j)); j--; s.add(s.get(i)+x);
把加入数据的过程和排序过程以及去掉相似项的过程都展示出来了。、
四、 心得总结
1. 递归方法不是解决算法效率问题的好方法。
2. 用java 实现算法的时候对泛型熟悉点时发现写代码还是比较简单的。当然，前提是算法的思
想要理解透彻。
3. 界面的实现用纯手工的方式比较麻烦。界面与后台代码的联络呼应没有很好的解决，就只好
用static 方法和变量来做了。
4. 什么事情还是要早作准备，不要临时抱佛脚。做一件事还是要认真做好。世上无难事，只要
focus ，而且focus 时间久点，应该没有太大问题。
...
五、 参考文献
1. 算法设计技巧与分析
2. 算法导论
子集和问题的完全多项式近似方案
２０１2年 2月
一、 作业背景：
1、 子集和问题简介
子集和问题的一个实例是一个对(S,t),其中S 是一个正整数的集合{x 1, x 2, x 3,..., x n },t 为一个正整数。这个判定问题是判定是否存在S 的一个子集，使得其中的数加起来恰为目标值t 。这个问题是NP 完全的。
与此判定问题相联系的最优化问题常常出现于实际应用中。在这种最优化问题中，希望找到
｛x1,x2……xn ｝的一个子集，是其中元素相加之和尽可能地大，但不能大于t 。例如, 假设我们有一辆能装不多于t 磅重的货的卡车，并有n 个不同的盒子要装运，其中第i 个的重量为xi 磅。要在不超过重量极限的前提下，将货尽可能的装满卡车。
2、 开发平台
Eclipse + Jdk 1.7
二、 问题分析：
子集和问题实际上是背包问题的特例, 就是背包问题中项的值和他们的大小相同。课本上给的算法实质就是个动态规划的方法。按照它给的伪代码实现之后，可以得出一个精确解。后来参考了算法导论书中对子集和采取的完全多项式时间近似方案来进行处理。
（一），给出一个指数时间的准确算法
假设对S 的每个子集S ’，都计算出S ’中所有元素的和。接着，在所有元素和不超过t 的子集中选择 其和最接近t 的那个子集。显然，这一算法将返回最优解。但它可能需要指数级的时间。为了实现这个算法，可以采用一个迭代过程：第i 轮迭代中，计算L +x 的所有子集的元素和，计算的基础是{x 1, x 2, x 3,..., x i -1}的所有子集和。在此计算过程中，一旦某个特定的子集S ’的和超过了t, 就没有必要再对它进行处理了，因为S ’的超集都不会成为最优解。下面给出这一策略的一个实现。
EXACT-SUBSET-SUM 的输入为一个集合S={x 1, x 2, x 3,..., x n }和一个目标值t ；这个过程以迭代的方式计算列表L i , 其中列出了{x 1, x 2, x 3,..., x i }的所有子集的和，这些和值都不超过目标值t 。接着，它返回L n 中的最大值。
如果L 是一个由正整数所构成的表，x 是一个正整数，我们用L +x 来表示通过对2中每个元素增i
2，3，5，9}，则L+2=｛3，4，5，7，11｝加x 而导出的整数列表。例如, 如果L ={1，。我们也对集合应用这
个记号，因而 S +x ={s +x :x ∈S }
我们还用到一个辅助过程MERGE-LISTS （L ，L ’），返回对它的两个已排序的输入列表L 和L ’合并及删除重复值后所产生的排序列表。
EXACT-SUBSET-SUM （S,t ）
1 n ← |S|
2 L0←
3 for I ← 1 to n
do L i ←MERGE-LIST(L i -1, L i +x )
remove from L i every element that is greater than t
return the largest element in L n
即P =P i -1 P i +x i , 可以通过对i 的归纳来证明，表L i 是一个包含P i 中所有值不大于t 的元素有序表。因为L i 的长度可大至2，一般来说EXACT-SUBSET-SUM 是一个指数时间的算法。
（二），完全多项式时间近似方案
对子集和问题我们可以导出一个完全多项式近似方案，在每个列表上L i 被创建后，对它进行”修整”，具体思想是如果其中有两个值比较接近，那么处于寻找近似解的目的，没有必要同时保存这两个数。更准确的说，我们采用一个修正参数δ，满足0
y ≤z ≤y (1+δ)
可以将这样一个z 看成是新表L ' 中代表y 的。每个y 都有一个满足不等式的z 的替换。如：
L ={10,11,12,15,20,21,22,23,24,29}
则可以休整L 而得
L ' ={10,12,15,20,23,29}
其中被删除的值11由10来代表，被删除的值21和22由20代表，被删除的值24由23代表。表的休整版本中的元素也是原表的元素，对一个表加以休整后，可以大大减少表中的元素，同时还可以在表中为每个人被从该表中删除的元素保留一个与其很接近的且略小一些的代表值。
在给定L 和δ的情况下，在时间O(m)内休整一个输入表L =,
假定L 已经排成单调递增序。该过程的输入是一个休整过的有序表。
TRIM （L ，δ）｛
1 m←|L |
2 L ’ ←
3 last←y 1
4 for i←2 to m
5 do if y i >last.(1+δ)
6 Then append y i onto the end of L ’
7 last←y i
Return L ’
｝
L 的元素被按照单调递增次序加以扫描，而一个数被加入返回的列表L ’中，仅当它是L 的第一个元素，或者如果它不能由最近被放入L ’的数来代表。
给定过程TRIM 后，可以如下构造近似方案。这个过程的输入为包含n 个整数的集合S={x 1, x 2, x 3,..., x n }（以任意次序放置），一个目标整数t,. 以及一个“近似参数”ε，此处：它返回一个值z ，该值落在最优解的 1+ε倍内。
APPROX-SUBSET-SUM （S, t, ∈）
1. n ←|S|
2. L 0←
3. for i ← to n
4. do L i ←MERGE-LISTS(L i -1，L i -1+x i )
5. L i ←TRIM(L i , ∈/2n )
6. Remove from L i every element that is greater than t
7. let z be the largest value in L n
8. return z
第2行将表L 0初始化为仅包含元素0的一个表。第3~ 6行间for 循环的效果是:将L i 作为
一个包含集合P i 的适当休整版本（去掉大于t 的元素）来计算. 因为L i 是从L i -1构造出来的，故必须保证重复的休整不会引入太多的不准确性。
例子如下:
S={104,102,201,101}
且t=308，ε=0.40.修整参数δ为 ε/8=0.05。、APPROX-SUBSET-SUM 在所指示的各行上计算出如下值: 第2行：L 0=
第4行: L 1=
第5行：L 1=
第6行：L 1=
第4行：L 2=
**
第5行：L 2=
第6行：L 2=
第4行：L 3=
第5行：L 3=
第6行：L 3=
第4行：L 4=
第5行：L 4=
第6行：L 4=
该返回值
z *=302作为答案。由于数据很短，所以我们可以看出最优答案为:307=104+102+101，而302是在 =40%内的。实际上，是在其 2% 之内。
关于APPROX-SUBSET-SUM 是关于子集和问题的一个完全多项式时间近似方案的证明，参见《算法导论》 第864页定理35.8。
（三），相关研究
为了做比较分析，在能求出准确解答的情况下，我们还用回溯法写了求精确解的方法。虽然能得出全部解答，但是如果子集项数稍微多一点基本上就得不出答案了。。。
代码如下：
public class SumOfSub {
private int w []; //用来存放子集 private int m ; //用来存放子集和t
private int x []; //用来判断该子集是否能用来构成目标子集和
public SumOfSub(int w[], int m, int n){ this . w = w; this . m = m; this . x = new int [n]; } public void computeSumOfSub(int s, int k, int r){ x [k] = 1; if (s+w [k] == m ){ printResult(k); } else if (s+w [k]+w [k+1]
//仍有别的可能可以继续求出别的方案, 不要当前的w[k]还有没有别的可能, 前提是已经排好序了
if (s+r-w [k]>=m && s+w [k+1]
}
效果如图：
x [k] = 0; computeSumOfSub(s, k+1, r-w [k]); } } public void printResult(int k){ for (int i=0; i
用动态规划的方案来解决这个问题代码如下：
Public class DP{
int [][] v={{0,0}};//用来放v[i][j]从x0到xi 中选出能组成j 的最优组合，这里是尽可能接近j
int left = t;// 将目标子集和大小付给剩下来要达到的大小 for (int i = 1; i left) { System. out .print("****"); v[i][j] = v[i - 1][j]; } else { // 如果当前的项与从前i-1项选出达到j-1的最优组合的和比v[i-1][j]的大 if (s[i] + v[i - 1][j - 1] > v[i - 1][j]) { v[i][j] = v[i - 1][j - 1]+s[i]; left -= s[i]; } else {
} } } } } } v[i][j] = v[i - 1][j]; System. out .println(" 动态规划" ); int j=t; int [] inOrout={}; for (int i=0;i
由于在java 中数组下表一直报错，在c++中修改代码之后得出效果如下：
三、 算法设计与实现：
核心代码如下：
Vector andSort(Vector s,int x,double e,int t){
//添加新元素到表中 int n=s.size(); for (int i=0;i vs=new Vector(); for (int index=0;index(1+e)*(vs.get(vs.size()-1)) && s.get(index)=0 && s.get(j)>temp){ } s.remove(j+1); s.add(j+1, temp); //s.add(j+1, s.get(j)); s.remove(j+1); s.add(j+1,s.get(j)); j--; s.add(s.get(i)+x);
把加入数据的过程和排序过程以及去掉相似项的过程都展示出来了。、
四、 心得总结
1. 递归方法不是解决算法效率问题的好方法。
2. 用java 实现算法的时候对泛型熟悉点时发现写代码还是比较简单的。当然，前提是算法的思
想要理解透彻。
3. 界面的实现用纯手工的方式比较麻烦。界面与后台代码的联络呼应没有很好的解决，就只好
用static 方法和变量来做了。
4. 什么事情还是要早作准备，不要临时抱佛脚。做一件事还是要认真做好。世上无难事，只要
focus ，而且focus 时间久点，应该没有太大问题。
...
五、 参考文献
1. 算法设计技巧与分析
2. 算法导论