Subset Sum CLRS 35.5, Part 1

May 27, 2014

We implement the algorithms exactly as CLRS gave them. First, here are the two auxiliary functions:

(define (list-add xs n)
  (map (lambda (x) (+ n x)) xs))

(define (merge-no-dups xs ys)
  (let loop ((xs xs) (ys ys) (zs (list)))
    (cond ((and (null? xs) (null? ys)) (reverse zs))
          ((null? xs) (loop xs (cdr ys) (cons (car ys) zs)))
          ((null? ys) (loop (cdr xs) ys (cons (car xs) zs)))
          ((< (car xs) (car ys)) (loop (cdr xs) ys (cons (car xs) zs)))
          ((< (car ys) (car xs)) (loop xs (cdr ys) (cons (car ys) zs)))
          (else (loop (cdr xs) (cdr ys) (cons (car xs) zs))))))

Next is the exact algorithm. Our iteration is slightly different than CLRS, but achieves the same result:

(define (exact-subset-sum xs t)
  (let loop ((xs xs) (ls (list 0)))
    (if (null? xs) (apply max ls)
      (loop (cdr xs)
            (filter (lambda (x) (<= x t))
              (merge-no-dups ls (list-add ls (car xs))))))))

Here is the example from CLRS:

> (exact-subset-sum '(1 4 5) 10)
10
> (exact-subset-sum '(1 4 5) 8
6

The trim function also uses a slightly different iteration that CLRS. For my money, the Scheme version using lists is clearer than the CLSR pseudocode using arrays, because the auxiliary variable to track the length of the array is no longer needed, but you may not agree. Notice that we kept the last variable, even though it is not strictly needed either since it is the same as (car ls):

(define (trim xs d)
  (let loop ((last (car xs)) (xs (cdr xs)) (ls (list (car xs))))
    (if (null? xs) (reverse ls)
      (if (< (* last (+ 1 d)) (car xs))
          (loop (car xs) (cdr xs) (cons (car xs) ls))
          (loop last (cdr xs) ls)))))

Then the approximate algorithm is similar to the exact algorithm:

(define (approx-subset-sum xs t e)
  (let ((len (length xs)))
    (let loop ((xs xs) (ls (list 0)))
      (if (null? xs) (apply max ls)
        (loop (cdr xs)
              (filter (lambda (x) (<= x t))
                (trim (merge-no-dups ls (list-add ls (car xs)))
                      (/ e 2 len))))))))

And here are some examples:

> (approx-subset-sum '(101 102 104 201) 308 0.4)
302
> (approx-subset-sum '(101 102 104 201) 308 0.1)
307
> (exact-subset-sum '(101 102 104 201) 308)
307

You can run the program at http://programmingpraxis.codepad.org/gcOgY3rQ.

Pages: 1 2

2 Responses to “Subset Sum CLRS 35.5, Part 1”

  1. Milbrae said

    It’s been some time since May 2014…. Taking a look at the exact-subset-sum function I’ve wondered how the “x” fits in there. Which vaues does it hold?

  2. programmingpraxis said

    @Milbrae: Filter runs over the list produced by merge-no-dups. Each element of the list is temporarily assigned to x, then compared to t, which is a parameter of the function. Filter returns a newly-allocated list that includes only those elements of the list produced by merge-no-dups that are less than or equal to t.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: