knapsack.hs

module Main where


superset xs = []:(superset' xs) -- remember the empty list
superset' (x:xs) = [x]:(map (x:) (superset' xs)) ++ superset' xs
superset' [] = []


items = [("Ant Repellent", 1, 2),
         ("Beer", 3, 9),
         ("Blanket", 4, 3),
         ("Bratwurst", 3, 8),
         ("Brownies", 3, 10),
         ("Frisbee", 1, 6),
         ("Salad", 5, 4),
         ("Watermelon", 10, 10)]


data Bag = Bag [([Char], Integer, Integer)] deriving Show


value = sum . map (\(_, _, x) -> x)
volume = sum . map (\(_, x, _) -> x)

bag_volume (Bag items) = volume items
bag_value (Bag items) = value items

instance Eq Bag where
   (Bag items1) == (Bag items2) =  (value items1) == (value items2)


instance Ord Bag where
   (Bag items1) `compare` (Bag items2) =  (value items1) `compare` (value items2)


knapsack max_volume items =
   maximum $ map Bag ok_volume where
      ok_volume = filter (\x -> volume x <= max_volume) $ superset items


main = do
   let best = knapsack 11 items
   print $ best
   putStrLn $ "max volume: " ++ (show $ bag_volume best)
   putStrLn $ "max value: " ++ (show $ bag_value best)