Editing Subset sum problem (section)

=== Fully-polynomial time approximation scheme{{Anchor|FPTAS}} ===
The following algorithm attains, for every <math>\epsilon>0</math>, an approximation ratio of <math>(1-\epsilon)</math>. Its run time is polynomial in {{mvar|n}} and <math>1/\epsilon</math>. Recall that ''n'' is the number of inputs and ''T'' is the upper bound to the subset sum.
 initialize a list ''L'' to contain one element 0.
 
 '''for each''' ''i'' from 1 to ''n'' '''do'''
     let ''U<sub>i</sub>'' be a list containing all elements ''y'' in ''L'', and all sums ''x<sub>i</sub>'' + ''y'' for all ''y'' in ''L''.
     sort ''U<sub>i</sub>'' in ascending order
     make ''L'' empty 
     let ''y'' be the smallest element of ''U<sub>i</sub>''
     add ''y'' to ''L''
     '''for each''' element ''z'' of ''U<sub>i</sub>'' in increasing order '''do'''
         <u>// Trim the list by eliminating numbers close to one another</u>
         <u>// and throw out elements greater than the target sum ''T''.</u>
         '''if''' ''y'' +  ''ε T''/''n'' < ''z'' ≤ ''T'' '''then'''
             ''y'' = ''z''
             add ''z'' to ''L''
 
 '''return''' the largest element in ''L.''

Note that without the trimming step (the inner "for each" loop), the list ''L'' would contain the sums of all <math>2^n</math> subsets of inputs. The trimming step does two things:

* It ensures that all sums remaining in ''L'' are below ''T'', so they are feasible solutions to the subset-sum problem.
* It ensures that the list L is "sparse", that is, the difference between each two consecutive partial-sums is at least <math>\epsilon T/n</math>. 

These properties together guarantee that the list {{mvar|L}} contains no more than <math>n/\epsilon</math> elements; therefore the run-time is polynomial in <math>n/\epsilon</math>.

When the algorithm ends, if the optimal sum is in {{mvar|L}}, then it is returned and we are done. Otherwise, it must have been removed in a previous trimming step.  Each trimming step introduces an additive error of at most <math>\epsilon T/n</math>,  so {{mvar|n}} steps together introduce an error of at most <math>\epsilon T</math>. Therefore, the returned solution is at least <math>\text{OPT}-\epsilon T</math> which is at least <math>(1-\epsilon)\text{OPT}</math> .

The above algorithm provides an ''exact'' solution to SSP in the case that the input numbers are small (and non-negative). If any sum of the numbers can be specified with at most {{mvar|P}} bits, then solving the problem approximately with <math>\epsilon = 2^{-P}</math> is equivalent to solving it exactly. Then, the polynomial time algorithm for approximate subset sum becomes an exact algorithm with running time polynomial in {{mvar|n}} and <math>2^P</math> (i.e., exponential in {{mvar|P}}).

Kellerer, Mansini, Pferschy and Speranza<ref>{{Cite journal|last1=Kellerer|first1=Hans|last2=Mansini|first2=Renata|last3=Pferschy|first3=Ulrich|last4=Speranza|first4=Maria Grazia|date=2003-03-01|title=An efficient fully polynomial approximation scheme for the Subset-Sum Problem|journal=Journal of Computer and System Sciences|language=en|volume=66|issue=2|pages=349–370|doi=10.1016/S0022-0000(03)00006-0|issn=0022-0000|doi-access=}}</ref> and Kellerer, Pferschy and Pisinger<ref name="knapsack">{{cite book|author1=Hans Kellerer|title=Knapsack problems|url=https://books.google.com/books?id=u5DB7gck08YC&pg=PA97|page=97|year=2004|publisher=Springer|isbn=9783540402862|author2=Ulrich Pferschy|author3=David Pisinger}}</ref> present other FPTASes for subset sum.