## 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.

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 […]

```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)
```