May 15, 2012 9:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
[…] today’s Programming Praxis exercise, our goal is to write that a function that gives the first possible […]
By Programming Praxis – Streaming Knapsack « Bonsai Code on May 15, 2012 at 12:12 PM
My Haskell solution (see http://bonsaicode.wordpress.com/2012/05/15/programming-praxis-streaming-knapsack/ for a version with comments):
By Remco Niemeijer on May 15, 2012 at 12:13 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.
By Axio on May 17, 2012 at 1:24 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)By Mike on May 17, 2012 at 11:34 PM