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

Posted by programmingpraxis
Filed in Exercises
4 Comments »

4 Responses to “Streaming Knapsack”

  1. Programming Praxis – Streaming Knapsack « Bonsai Code said
    May 15, 2012 at 12:12 PM

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

  2. Remco Niemeijer said
    May 15, 2012 at 12:13 PM

    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
    May 17, 2012 at 1:24 PM

    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
    May 17, 2012 at 11:34 PM

    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 comment