The Subset-sum Problem
The subset-sum problem: An instance of the subset-sum problem is a pair (S, t), where S is a set {x1, x2, ..., xn} of positive integers and t is a positive integer. This decision problem asks whether there exists a subset of S that adds up exactly to the target value t. This problem is NP-complete.
- The optimization problem associated with this decision problem arises in practical applications. In the optimization problem, we wish to find a subset of {x1, x2, ..., xn} 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 t pounds, and n different boxes to ship, the ith of which weighs xi pounds. We wish to fill the truck with as heavy a load as possible without exceeding the given weight limit.
- 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/∈ as well as in the size of the input.)
An exponential-time exact algorithm: Suppose that we computed, for each subset S′ of S, the sum of the elements in S′, and then we selected, among the subsets whose sum does not exceed t, the one whose sum was closest to t. Clearly this algorithm would return the optimal solution, but it could take exponential time. To implement this algorithm, we could use an iterative procedure that, in iteration i, computes the sums of all subsets of {x1, x2, ..., xi}, using as a starting point the sums of all subsets of {x1, x2, ..., xi-1}. In doing so, we would realize that once a particular subset S′ had a sum exceeding t, there would be no reason to maintain it, since no superset of S′ could be the optimal solution. We now give an implementation of this strategy.
The procedure EXACT-SUBSET-SUM takes an input set S = {x1, x2, ..., xn} and a target value t; we'll see its pseudocode in a moment. This procedure iteratively computes Li, the list of sums of all subsets of {x1, ..., xi} that do not exceed t, and then it returns the maximum value in Ln.
If L is a list of positive integers and x is another positive integer, then we let L x denote the list of integers derived from L by increasing each element of L by x. For example, if L = 〈1, 2, 3, 5, 9〉, then L 2 = 〈3, 4, 5, 7, 11〉. We also use this notation for sets, so that
S x = {s x : s ∈ S}.
We also use an auxiliary procedure MERGE-LISTS(L, L′) that returns the sorted list that is the merge of its two sorted input lists L and L′ with duplicate values removed. Like the MERGE procedure we used in merge sort, MERGE-LISTS runs in time O(|L| |L′|). (We omit giving pseudocode for MERGE-LISTS.)
EXACT-SUBSET-SUM(S, t) 1 n ← |S| 2 L0 ← 〈0〉 3 for i ← 1 to n 4 do Li ← MERGE-LISTS(Li-1, Li-1 xi) 5 remove from Li every element that is greater than t 6 return the largest element in Ln
To see how EXACT-SUBSET-SUM works, let Pi denote the set of all values that can be obtained by selecting a (possibly empty) subset of {x1, x2, ..., xi} and summing its members. For example, if S = {1, 4, 5}, then
|
P1 |
= |
{0, 1} , |
|
P2 |
= |
{0, 1, 4, 5} , |
|
P3 |
= |
{0, 1, 4, 5, 6, 9, 10} . |
Given the identity
we can prove by induction on i that the list Li is a sorted list containing every element of Pi whose value is not more than t. Since the length of Li can be as much as 2i, EXACT-SUBSET-SUM is an exponential-time algorithm in general, although it is a polynomial-time algorithm in the special cases in which t is polynomial in |S| or all the numbers in S are bounded by a polynomial in |S|.
A fully polynomial-time approximation scheme: We can derive a fully polynomial-time approximation scheme for the subset-sum problem by "trimming" each list Li after it is created. The idea is that if two values in L are close to each other, then for the purpose of finding an approximate solution there is no reason to maintain both of them explicitly. More precisely, we use a trimming parameter δ such that 0 < δ < 1. To trim a list L by δ 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 still in L′ that approximates y, that is,
We can think of such a z as "representing" y in the new list L′. Each y is represented by a z satisfying inequality (35.22). For example, if δ = 0.1 and
L = 〈10, 11, 12, 15, 20, 21, 22, 23, 24, 29〉,