Streaming Knapsack

May 15, 2012

This is a problem of dynamic programming. Construct a matrix with k rows numbered 0 to k−1 and n columns numbered 1 to n. All the cells of the matrix are initially empty, except that the cells in row 0 each contain the null list (which must be distinguishable from an empty cell). Then the items of the input stream are read in order. For each item x, a solution is found and processing stops if cell (k−1,nx) is non-empty; the solution is the list of items in cell (k−1,nx) plus item x. Otherwise, for each non-empty cell (r,c) in the matrix, if r+1<k and c+x<n and cell (r+1,c+x) is empty, then cell (r+1,c+x) is updated to contain the list of items in cell (r,c) plus the new item x.

Since the matrix is sparse, we will use a hash table keyed by (r,c) instead of a matrix, and for demonstration we will use a random number generator to provide a stream of positive integers:

(define (streaming-knapsack k n)
  (define (hash rc) (+ (car rc) (* n (cdr rc))))
  (let ((table (make-hash hash equal? #f 997)))
    (let loop ((x (+ (randint n) 1)))
      (display x) (newline)
      (cond ((table 'lookup (cons (- k 1) (- n x))) =>
              (lambda (xs) (cons x xs)))
      (else (let loop ((xs (table 'enlist)))
              (when (pair? xs)
                (let* ((rcs (car xs)) (r (caar rcs)) (c (cdar rcs))
                       (s (cdr rcs)) (r1 (+ r 1)) (cx (+ c x)))
                  (when (and (< r1 k) (< cx n)
                             (not (table 'lookup (cons r1 cx))))
                    (table 'insert (cons r1 cx) (cons x s))))
                (loop (cdr xs))))
            (when (not (table 'lookup (cons 1 x)))
              (table 'insert (cons 1 x) (list x)))
            (loop (+ (randint n) 1)))))))

The outer loop runs once for each item in the input stream; since we are generating the input stream on the fly, it displays each stream element as it passes through. The first clause of the cond looks for the (r−1, c−x) item in the hash table and returns a result if it exists. If not, the else clause of the cond loops over all the items in the hash table, adds a new table item if all the tests pass, adds a (1 x) table item if it doesn’t exist, and loops to the next element in the input stream.

In practice, you should replace the expression (+ (randint n) 1), which occurs twice, with a function that gets the next item from the input stream, and pass the function as a parameter to streaming-knapsack.

We used hash tables and the random-number generator from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/WHdBXcyr.

About these ads

Pages: 1 2

4 Responses to “Streaming Knapsack”

  1. [...] today’s Programming Praxis exercise, our goal is to write that a function that gives the first possible [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2012/05/15/programming-praxis-streaming-knapsack/ for a version with comments):

    import Data.List
    
    knapsack :: Num a => Int -> a -> [a] -> Maybe [a]
    knapsack k n = find (\s -> length s == k && sum s == n) . subsequences
    
  3. Axio said

    I guess the efficient idea is just to compute the simple knapsack problem of finding k elements that sum to n, using dynamic programming “backwards”, i.e. without doing recursive calls but instead using KP[S][N], to find KP[S+e][N] where the list (S+e) is (append S (list e)).
    No time to code it now, though.

  4. Mike said

    Python 2.7

    This first solution is similar to the praxis solution, using a map as a sparce array. I use (remaining items, remaining sum) as the key.

    def knapsack(s, k, n):
        d = {(k,n):[]}
        
        for e in s:
            if (1, e) in d:
                return d[(1, e)] + [e]
            
            d.update( ((j-1, m-e), v+[e]) for (j, m), v in d.items()
                                if j > 0 and m >= e and (j-1, m-e) not in d)
    

    This second solution is similar to Remco’s. subsequences(seq, k) reads items from ‘seq’ and yields a stream of k-tuples ending at the most recently read item.

    from itertools import combinations, ifilter
    
    def subsequences(seq, k):
        items = []
        for item in seq:
            for subseq in combinations(items, k-1):
                yield subseq + (item,)
                
            items.append(item)
    
    def knapsack(seq, k, n):
        return next(ifilter(lambda x:sum(x) == n, subsequences(seq, k)), None)
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 628 other followers

%d bloggers like this: