Knapsack

In [1]:

    

newtype Item = Item (Int, Int) deriving (Show)

weight :: Item -> Int
weight (Item (w, _)) = w

value :: Item -> Int
value (Item (_, v)) = v


    

In [2]:

    

import System.Random

sampleItems n = zipWith (curry Item) weights values
    where
    (weights, values) = splitAt n $ take (2*n) rseq
    rseq = randomRs (1, 20) (mkStdGen 32345)
sampleItems 5


    

    






[Item (12,7),Item (6,16),Item (12,13),Item (9,2),Item (4,16)]

In [3]:

    

knapsack :: Int -> [Item] -> Int
knapsack _ [] = 0
knapsack w (x:xs)
    | w < weight x = knapsack w xs
    | otherwise = maximum ((knapsack w xs), (knapsack (w - weight x) xs) + value x)


sample = sampleItems 10000
knapsack 5000 sample


    

    






5109

In [ ]:

    

maximum (2, 4)


    

In [ ]: