Posts Tagged ‘knapsack’

Programming Praxis – Streaming Knapsack

May 15, 2012

In today’s Programming Praxis exercise, our goal is to write that a function that gives the first possible knapsack, i.e. the first combination of k values that sum up to a given value n, from a lazy list. The list should not be evaluated further than necessary. Let’s get started, shall we?

Some imports:

import Data.List
import Debug.Trace
import System.IO

Rather than constructing a matrix we use a solution that probably isn’t as efficient, but significantly more compact and easy to understand. Just take all possible combinations of numbers and find the first one of length k that sums up to n.

knapsack :: Num a => Int -> a -> [a] -> Maybe [a]
knapsack k n = find (\s -> length s == k && sum s == n) . subsequences

To demonstrate that the function is indeed lazy, we apply it to a list that indicates when one of its elements is evaluated. The hFlush is to make sure the result of the first function is printed before the second list gets evaluated, since without it the two results will be printed at the end.

main :: IO ()
main = do print . knapsack 7 37 $ map debugEval [1..20]
          hFlush stdout
          print . knapsack 7 17 $ map debugEval [1..20]
    where debugEval n = trace ("evaluated: " ++ show n) n