Editing Subset sum problem (section)

=== Simple 1/2-approximation ===
The following very simple algorithm has an approximation ratio of 1/2:<ref name=":1">{{Cite journal|last1=Caprara|first1=Alberto|last2=Kellerer|first2=Hans|last3=Pferschy|first3=Ulrich|date=2000-02-01|title=The Multiple Subset Sum Problem|url=https://doi.org/10.1137/S1052623498348481|journal=SIAM Journal on Optimization|volume=11|issue=2|pages=308–319|doi=10.1137/S1052623498348481|issn=1052-6234}}</ref>

* Order the inputs by descending value;
* Put the next-largest input into the subset, as long as it fits there.

When this algorithm terminates, either all inputs are in the subset (which is obviously optimal), or there is an input that does not fit. The first such input is smaller than all previous inputs that are in the subset and the sum of inputs in the subset is more than ''T''/2 otherwise the input also is less than T/2 and it would fit in the set. Such a sum greater than T/2  is obviously more than OPT/2.