## 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,*n*−*x*) is non-empty; the solution is the list of items in cell (*k*−1,*n*−*x*) 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.

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

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

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.

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.

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.