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.

About these ads

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

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

    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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 627 other followers

%d bloggers like this: