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