## Streaming Knapsack

### May 15, 2012

A famous problem of computer science is the knapsack problem, in which you are to find a combination of items from a population that sums to a given target, often with some kind of constraint such as maximizing the value of the items. In today’s problem we want to find the first possible combination of *k* integers from a stream of positive integers that sum to *n*. For instance, given the input stream 4, 8, 9, 2, 10, 2, 17, 2, 12, 4, 5, …, we want to find the knapsack containing 4, 2, 10, 2, 2 immediately after reading the third 2, without reading the 12, 4, 5 that follow it.

Your task is to write a program that takes parameters *k* and *n* and an input stream and returns the first possible knapsack. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

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