子集和问题的完全多项式近似方案算法.docxVIP

子集和问题的完全多项式近似方案算法

子集和问题的完全多项式近似方案

２０１2年2月

一、作业背景：

1、子集和问题简介

子集和问题的一个实例是一个对(S,t),其中S是一个正整数的集合{x1,x2,x3,...,xn},t为一个正整数。这个判定问题是判定是否存在S的一个子集，使得其中的数加起来恰为目标值t。这个问题是NP完全的。

与此判定问题相联系的最优化问题常常出现于实际应用中。在这种最优化问题中，希望找到

｛x1,x2……xn｝的一个子集，是其中元素相加之和尽可能地大，但不能大于t。例如,假设我们有一辆能装不多于t磅重的货的卡车，并有n个不同的盒子要装运，其中第i个的重量为xi磅。要在不超过重量极限的前提下，将货尽可能的装满卡车。

2、开发平台

Eclipse+Jdk1.7

二、问题分析：

子集和问题实际上是背包问题的特例,就是背包问题中项的值和他们的大小相同。课本上给的算法实质就是个动态规划的方法。按照它给的伪代码实现之后，可以得出一个精确解。后来参考了算法导论书中对子集和采取的完全多项式时间近似方案来进行处理。

（一），给出一个指数时间的准确算法

假设对S的每个子集S’，都计算出S’中所有元素的和。接着，在所有元素和不超过t的子集中选择其和最接近t的那个子集。显然，这一算法将返回最优解。但它可能需要指数级的时间。为了实现这个算法，可以采用一个迭代过程：第i轮迭代中，计算L+x的所有子集的元素和，计算的基础是{x1,x2,x3,...,xi-1}的所有子集和。在此计算过程中，一旦某个特定的子集S’的和超过了t,就没有必要再对它进行处理了，因为S’的超集都不会成为最优解。下面给出这一策略的一个实现。

EXACT-SUBSET-SUM的输入为一个集合S={x1,x2,x3,...,xn}和一个目标值t；这个过程以迭代的方式计算列表Li,其中列出了{x1,x2,x3,...,xi}的所有子集的和，这些和值都不超过目标值t。接着，它返回Ln中的最大值。

如果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）

1n←|S|

2L0←

3forI←1ton

doLi←MERGE-LIST(Li-1,Li+x)

removefromLieveryelementthatisgreaterthant

returnthelargestelementinLn

即P=Pi-1Pi+xi,可以通过对i的归纳来证明，表Li是一个包含Pi中所有值不大于t的元素有序表。因为Li的长度可大至2，一般来说EXACT-SUBSET-SUM是一个指数时间的算法。

（二），完全多项式时间近似方案

对子集和问题我们可以导出一个完全多项式近似方案，在每个列表上Li被创建后，对它进行”修整”，具体思想是如果其中有两个值比较接近，那么处于寻找近似解的目的，没有必要同时保存这两个数。更准确的说，我们采用一个修正参数δ，满足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已经排成单调递增序。该过程的输入是