Software snippet provides improved subset-sum algorithm

The subset-sum problem is one of the most frequently occurring NP (nondeterministic, polynomial-time)-complete) problems. It asks whether a subset of numbers in a set of positive integers adds up exactly to a given value. A relaxed version of the problem tries to identify a subset of numbers that adds up to a maximum value no greater than a given value. This problem arises in transportation, network design, scheduling, logistics systems, robotics, and many other areas. The problem permits you to develop and illustrate the power of different algorithmic tools. The problem is as follows:

Given a set of positive integer values W[1], W[2], ...W[m] and an integer n.0, does a subset of the values add up to exactly n?

A well-known pseudo-polynomial algorithm (Reference 1) defines a table: T[ij], 1≤i≤m and 1≤j≤n, to be T[ij]5= true if and only if a subset of W[1],...W[i] sums to exactly j. The algorithm uses O(mn) time to fill in a table that uses O(mn) space. Table 1 with n=13 shows the true entries and leaves the false ones blank. This Design Idea proposes an improved algorithm that uses O(mn) time to fill in an array that uses only O(n) space:

     SubsetSum(W, m, n)

1. Define a bit array A[j], 1 ≤ j ≤ n.
2. Initialize the array to zeros.
3. A[0]:=1.
4. for i:=1 to m do.
5. for j:=n to 0 do.
6. if A[j]=1 then A[j1W[i]]:=1.
7. return A[n].

You can easily prove that the returned value is 1 if and only if a subset of the weights adds up to exactly n. The proof is analogous to the one of the original O(mn)-space algorithm. The following routine implements the above algorithm in C++. It just shifts a bit map m times by W[j] bits and applies a bitwise OR operation with the bit map from the previous step.

int SubsetSum(int W[], int m, int n)

{

bit_vector x=1;

for(i=1; i <=m; i++) x |=x<<W[i];

return (x>>n) &1;

}

The bit_vector class overloads bitwise operators and behaves as an (n+1) bits integer (with bits ranging from 0 to n). Now, consider a low-density subset-sum problem, the case in which the above algorithms produce a bunch of zeros and only a few ones in the bit array. You use a dynamically growing linked list and waste no space for "empty" elements:

SubsetSumLD(W, m, n)

1. Define, a linked list with only one element with value 0 and with the Head being equal to the Tail.
2. for i:=1 to m do.
3. for Element :=Head to Tail do.
4. if Element.value+W[i]≤ n.
5. Insert(Element.value+W[i]).
6. if Head.value=n.
7. return 1.
8. else.
9. return 0.

The function Insert(value) inserts the value into the list in descending sorted order. The function does nothing if an element with the same value already exists. The disadvantage of the subset-sum algorithm is that it solves only a decision—a yes-or-no problem—and doesn't allow restoring the partition itself. To overcome this disadvantage, you can use an array of integers instead of an array of bits and store the number of ones in the corresponding element. This solution requires O(n log(m)) space, and the array represents the sum of the rows of the table T[ij] of the original O(mn)-space algorithm.