Programming Praxis

We studied the subset sum problem — find the subset of a set of integers that sum to a given target — in two previous exercises; in both cases, we produced an exact answer, but took exponential time to do so. In today’s exercise, we will study a variant of the subset sum problem — find the subset of a set of integers that have the largest sum not exceeding a given target — that admits both exact and approximate answers; the exact answer runs in exponential time, though it is typically quite fast, but the approximate answer runs in linear time in the number of integers in the input set. Our solution is given by CLRS 35.5.

The exact solution uses two auxiliary functions. The function denoted by L + x adds x to each element of a list L. The function merge-lists takes two sorted input lists and returns the merge of the two lists with duplicates removed. Then CLRS gives the algorithm as follows, where S is a sorted list of integers and t is the target:

EXACT-SUBSET-SUM(S,t)
1  n = |S|
2  L₀ = ‹0›
3  for i = 1 to n
4      L_i = MERGE-LISTS(L_i−1, L_i−1 + x)
5      remove from L_i every element that is greater than t
6  return the largest element in L_n

The approximation algorithm adds a trimming step to the exact algorithm. The trimming step removes from the accumulating L list partial sums that are within a factor of 0 < δ < 1 such that any partial sum that is less than 1 + δ times its predecessor is removed. For instance, given L = ‹10, 11, 12, 15, 20, 21, 22, 23, 24, 29› and δ = 0.1, the trimmed L‘ = ‹10, 12, 15, 20, 23, 24›, where 11 is removed because it is within 10% of 10 and 21 and 22 are removed because they are within 10% of 20; trim assumes that L = ‹y₁, y₂,… y_m› is sorted:

TRIM(L,δ)
1  let m be the length of L
2  L‘ = ‹y₁›
3  last = y₁
4  for i = 2 2 m
5      if y_i > last · (1 + δ) // y_i ≥ last because L is sorted
6           append y_i onto the end of L‘
7          last = y_i
8  return L‘

Then the approx-subset-sum algorithm is the same as the exact-subset-sum algorithm except that step L_i = TRIM(L_i, ε/2n) is inserted between steps 4 and 5, where the solution is within 0 < ε < 1 percent of the desired target.

Your task is to implement the two algorithms given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2