chap37.htm

介绍算法的书籍

<P>







<h1><a name="0a23_1d48">37.4 The subset-sum problem<a name="0a23_1d48"></h1><P>
<a name="0a23_1d45"><a name="0a23_1d46"><a name="0a23_1d47">An instance of the subset-sum problem is a pair (<I>S</I>, <I>t</I>), where <I>S</I> is a set {<I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>n</I></SUB>} of positive integers and <I>t</I> is a positive integer. This decision problem asks whether there exists a subset of <I>S</I> that adds up exactly to the target value <I>t</I>. This problem is NP-complete (see Section 36.5.3).<P>
The optimization problem associated with this decision problem arises in practical applications. In the optimization problem, we wish to find a subset of {<I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>n</I></SUB>} whose sum is as large as possible but not larger than t. For example, we may have a truck that can carry no more than <I>t </I>pounds, and <I>n</I> different boxes to ship, the <I>i</I>th of which weighs <I>x<SUB>i</I></SUB> pounds. We wish to fill the truck as full as possible without exceeding the given weight limit.<P>
In this section, we present an exponential-time algorithm for this optimization problem and then show how to modify the algorithm so that it becomes a fully polynomial-time approximation scheme. (Recall that a fully polynomial-time approximation scheme has a running time that is polynomial in 1/ <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT> as well as in <I>n</I>.)<P>





<h2>An exponential-time algorithm</h2><P>
If <I>L</I> is a list of positive integers and <I>x</I> is another positive integer, then we let <I>L</I> + <I>x</I> denote the list of integers derived from <I>L</I> by increasing each element of <I>L</I> by <I>x</I>. For example, if <I>L</I> = <img src="../images/lftwdchv.gif">1, 2, 3, 5, 9<img src="../images/wdrtchv.gif">, then <I>L</I> + 2 = <img src="../images/lftwdchv.gif">3, 4, 5, 7, 11<img src="../images/wdrtchv.gif">. We also use this notation for sets, so that<P>
<pre><I>S</I> + <I>x</I> = {<I>s</I> + <I>x</I> : <I>s</I> <img src="../images/memof12.gif"> <I>S</I>} .</sub></sup></pre><P>
<a name="0a24_1d48">We use an auxiliary procedure <FONT FACE="Courier New" SIZE=2>MERGE</FONT>-<FONT FACE="Courier New" SIZE=2>LISTS</FONT>(<I>L</I>, <I>L</I>') that returns the sorted list that is the merge of its two sorted input lists <I>L</I> and <I>L</I>'. Like the <FONT FACE="Courier New" SIZE=2>MERGE</FONT> procedure we used in merge sort (Section 1.3.1), M<FONT FACE="Courier New" SIZE=2>ERGE-</FONT>L<FONT FACE="Courier New" SIZE=2>ISTS </FONT>runs in time <I>O</I>(|<I>L</I>| + |<I>L</I>'|). (We omit giving pseudocode for M<FONT FACE="Courier New" SIZE=2>ERGE-</FONT><FONT FACE="Courier New" SIZE=2>LISTS</FONT>.) The procedure E<FONT FACE="Courier New" SIZE=2>XACT-</FONT>S<FONT FACE="Courier New" SIZE=2>UBSET-</FONT><FONT FACE="Courier New" SIZE=2>SUM</FONT> takes an input set <I>S</I> = {<I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>n</I></SUB>} and a target value <I>t</I>.<P>
<pre><a name="0a24_1d49">EXACT-SUBSET-SUM(<I>S</I>, <I>t</I>)</sub></sup></pre><P>
<pre>1  <I>n</I> <img src="../images/arrlt12.gif"> |<I>S</I>|</sub></sup></pre><P>
<pre>2  <I>L</I><SUB>0</SUB> <img src="../images/arrlt12.gif"> <img src="../images/lftwdchv.gif">0<img src="../images/wdrtchv.gif"></sub></sup></pre><P>
<pre>3  <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>4  <B>do</B> <I>L<SUB>i</I></SUB> <img src="../images/arrlt12.gif"> MERGE-LISTS(<I>L<SUB>i-</I>1</SUB>, <I>L<SUB>i-</I>1 </SUB>+ <I>x<SUB>i</I></SUB>)</sub></sup></pre><P>
<pre>5  remove from <I>L<SUB>i</I></SUB> every element that is greater than <I>t</I></sub></sup></pre><P>
<pre>6  <B>return</B> the largest element in <I>L<SUB>n</I></sub></sup></pre><P>
Let <I>P<SUB>i</I></SUB> denote the set of all values that can be obtained by selecting a (possibly empty) subset of {<I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>i</I></SUB>} and summing its members. For example, if <I>S</I> = {1, 4, 5}, then<P>
<pre><I>P</I><SUB>1</SUB> = {0, 1} ,</sub></sup></pre><P>
<pre><I>P</I><SUB>2</SUB> = {0, 1, 4, 5} ,</sub></sup></pre><P>
<pre><I>P</I><SUB>3</SUB> = {0, 1, 4, 5, 6, 9, 10} .</sub></sup></pre><P>
Given the identity<P>
<img src="979_a.gif"><P>
<h4><a name="0a24_1d4a">(37.11)<a name="0a24_1d4a"></sub></sup></h4><P>
we can prove by induction on <I>i</I> (see Exercise 37.4-1) that the list <I>L<SUB>i</I></SUB> is a sorted list containing every element of <I>P<SUB>i</I></SUB> whose value is not more than <I>t</I>. Since the length of <I>L<SUB>i</I></SUB> can be as much as 2<I><SUP>i</I></SUP>, E<FONT FACE="Courier New" SIZE=2>XACT-</FONT>S<FONT FACE="Courier New" SIZE=2>UBSET-</FONT><FONT FACE="Courier New" SIZE=2>SUM</FONT> is an exponential-time algorithm in general, although it is a polynomial-time algorithm in the special cases in which <I>t</I> is polynomial in |<I>S</I>| or all of the numbers in <I>S</I> are bounded by a polynomial in |<I>S</I>|.<P>
<P>







<h2>A fully polynomial-time approximation scheme</h2><P>
<a name="0a25_1d4a">We can derive a fully polynomial-time approximation scheme for the subset-sum problem by &quot;trimming&quot; each list L<SUB>i</SUB> after it is created. We use a trimming parameter <img src="../images/delta12.gif"> such that 0 &lt; <img src="../images/delta12.gif"> &lt; 1. To trim a list L by <img src="../images/delta12.gif"> means to remove as many elements from L as possible, in such a way that if L'is the result of trimming L, then for every element y that was removed from L, there is an element z <img src="../images/lteq12.gif"> y still in L' such that <P>
<img src="980_a.gif"><P>
or, equivalently,<P>
<pre>(1 - <img src="../images/delta12.gif">)<I>y</I> <img src="../images/lteq12.gif"> <I>z</I> <img src="../images/lteq12.gif"> <I>y</I> .</sub></sup></pre><P>
We can think of such a <I>z</I> as &quot;representing&quot; <I>y</I> in the new list <I>L</I>'. Each <I>y</I> is represented by a <I>z</I> such that the relative error of <I>z</I>, with respect to <I>y</I>, is at most <img src="../images/delta12.gif">. For example, if <img src="../images/delta12.gif"> = 0.1 and<P>
<pre><I>L</I> = <img src="../images/lftwdchv.gif">10, 11, 12, 15, 20, 21, 22, 23, 24, 29<img src="../images/wdrtchv.gif">,</sub></sup></pre><P>
then we can trim <I>L</I> to obtain<P>
<pre><I>L</I>' = <img src="../images/lftwdchv.gif">10, 12, 15, 20, 23, 29<img src="../images/wdrtchv.gif">,</sub></sup></pre><P>
where the deleted value 11 is represented by 10, the deleted values 21 and 22 are represented by 20, and the deleted value 24 is represented by 23. It is important to remember that every element of the trimmed version of the list is also an element of the original version of the list. Trimming a list can dramatically decrease the number of elements in the list while keeping a close (and slightly smaller) representative value in the list for each element deleted from the list.<P>
The following procedure trims an input list <I>L</I> = <img src="../images/lftwdchv.gif"><I>y</I><SUB>1</SUB>, <I>y</I><SUB>2</SUB>, . . . , <I>y<SUB>m</SUB></I><img src="../images/wdrtchv.gif"> in time <img src="../images/bound.gif">(<I>m</I>), assuming that <I>L</I> is sorted into nondecreasing order. The output of the procedure is a trimmed, sorted list.<P>
<pre><a name="0a25_1d4b">TRIM(L, <img src="../images/delta12.gif">)</sub></sup></pre><P>
<pre>1  m <img src="../images/arrlt12.gif"> <img src="../images/lteq12.gif">|L|</sub></sup></pre><P>
<pre>2  L' <img src="../images/arrlt12.gif"> &lt;y<SUB>1</SUB>&gt;</sub></sup></pre><P>
<pre>3  last <img src="../images/arrlt12.gif"> &lt;y<SUB>1</SUB>&gt;</sub></sup></pre><P>
<pre>4<B>  for</B> i <img src="../images/arrlt12.gif"> 2 <B>to</B> m</sub></sup></pre><P>
<pre>5<B>       do if</B> last &lt; (1 - <img src="../images/delta12.gif">)y<SUB>i</sub></sup></pre><P>
<pre>6<B>             then</B> append y<SUB>i </SUB>onto the end of L'</sub></sup></pre><P>
<pre>7                  last <img src="../images/arrlt12.gif"> y<SUB>i</sub></sup></pre><P>
<pre>8<B>  return</B> L'</sub></sup></pre><P>
The elements of <I>L</I> are scanned in increasing order, and a number is put into the returned list <I>L</I>' only if it is the first element of <I>L</I> or if it cannot be represented by the most recent number placed into <I>L</I>'.<P>
Given the procedure <FONT FACE="Courier New" SIZE=2>TRIM</FONT>, we can construct our approximation scheme as follows. This procedure takes as input a set <I>S</I> = {<I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, <I>. . . </I>, <I>x<SUB>n</I></SUB>} of <I>n</I> integers (in arbitrary order), a target integer <I>t</I>, and an "approximation parameter" <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT>, where 0 &lt; <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT> &lt; 1.<P>
<pre><a name="0a25_1d4c">APPROX-SUBSET-SUM(<I>S, t, </I><img src="../images/memof12.gif">)</sub></sup></pre><P>
<pre>1<I>  n</I> <img src="../images/arrlt12.gif"> |<I>S</I>|</sub></sup></pre><P>
<pre>2  <I>L</I><SUB>0</SUB> <img src="../images/arrlt12.gif"> <img src="../images/lftwdchv.gif">0<img src="../images/wdrtchv.gif"></sub></sup></pre><P>
<pre>3<B>  for</B> <I>i</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>4<B>       do</B> <I>L<SUB>i</I></SUB> <img src="../images/arrlt12.gif"> MERGE-LISTS(<I>L<SUB>i</I></SUB>-<SUB>1</SUB>, <I>L<SUB>i</I></SUB>-<SUB>1</SUB> + <I>x<SUB>i</I></SUB>)</sub></sup></pre><P>
<pre>5<I>          L<SUB>i</I></SUB> <img src="../images/arrlt12.gif"> TRIM(<I>L<SUB>i</I>, </SUB><img src="../images/memof12.gif"> / <I>n</I>)</sub></sup></pre><P>
<pre>6          remove from <I>L<SUB>i</I></SUB> every element that is greater than <I>t</I></sub></sup></pre><P>
<pre>7  let <I>z</I> be the largest value in <I>L<SUB>n</I></sub></sup></pre><P>
<pre>8<B>  return</B> <I>z</I></sub></sup></pre><P>
Line 2 initializes the list <I>L</I><SUB>0</SUB> to be the list containing just the element 0. The loop in lines 3-6 has the effect of computing <I>L<SUB>i</I></SUB> as a sorted list containing a suitably trimmed version of the set <I>P<SUB>i</I></SUB>, with all elements larger than <I>t</I> removed. Since <I>L<SUB>i</I></SUB> is created from <I>L<SUB>i</I></SUB>-<SUB>1</SUB>, we must ensure that the repeated trimming doesn't introduce too much inaccuracy. In a moment, we shall see that <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-<FONT FACE="Courier New" SIZE=2>SUBSET</FONT>-<FONT FACE="Courier New" SIZE=2>SUM</FONT> returns a correct approximation if one exists.<P>
As an example, suppose we have the instance<P>
<pre><I>L</I> = <img src="../images/lftwdchv.gif">104, 102, 201, 101<img src="../images/wdrtchv.gif"></sub></sup></pre><P>
with <I>t</I> = 308 and <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT> = 0.20. The trimming parameter <img src="../images/delta12.gif"> is <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"> </FONT>/ 4 = 0.05. <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-<FONT FACE="Courier New" SIZE=2>SUBSET</FONT>-<FONT FACE="Courier New" SIZE=2>SUM</FONT> computes the following values on the indicated lines:<P>
<pre>line 2:  <I>L</I><SUB>0</SUB>  =  <img src="../images/lftwdchv.gif">0<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>
<pre>line 4:  <I>L</I><SUB>1  </SUB>=  <img src="../images/lftwdchv.gif">0, 104<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>
<pre>line 5:  <I>L</I><SUB>1  </SUB>=  <img src="../images/lftwdchv.gif">0, 104<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>
<pre>line 6:  <I>L</I><SUB>1  </SUB>=  <img src="../images/lftwdchv.gif">0, 104<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>