knapsack.hs

module Knapsack where
import Control.Monad
import Data.Array
import Data.List

data Item a = Item { item      :: a, 
                     itemValue :: Int, 
                     itemSize  :: Int }
    deriving (Eq, Show, Ord)

data Cell a = Cell (Int, [Item a]) 
    deriving (Eq, Show, Ord)

pack :: Int -> [Item a] -> Cell a
pack size items = valOf noItems size
    where 
        noItems  = length items
        itemsArr = listArray (1,noItems) items
        itemNo n = itemsArr ! n

        table    = array ((1,1),(noItems,size)) $ 
                   [
                       ((m, n), cell m n) |
                       m <- [1..noItems], 
                       n <- [1..size] 
                   ]

        valOf m n 
         | m < 1 || n < 1 = Cell (0, [])
         | otherwise      = table ! (m,n)

        cell m n = 
            case itemNo m of
                i@(Item _ v s)
                 | s  > n    ||
                   vL >= vU + v -> Cell (vL    ,   isL)
                 | otherwise    -> Cell (vU + v, i:isU)
                 where
                     Cell (vL, isL) = valOf (m - 1) n
                     Cell (vU, isU) = valOf (m - 1) (n - s)