knapsack :: Int           -- Bag size
         -> Int           -- Number of items
         -> Array Int Int -- Item weights
         -> Array Int Int -- Item values
         -> Int           -- The max value we can hold in the bag
knapsack size numItems values weights = table!(size,numItems)
  where    
   table = array ((0,0), (size,numItems))
                 [(i, f i) | i <- range ((0,0), (size,numItems))]
   f (s,i) | s == 0              = 0              -- If bag size is zero 
           | i == 0              = 0              -- If we don't take any items
           | s-weights!(i-1) < 0 = table!(s,i-1)  -- If the item is too big
           | otherwise = max (values!(i-1) + table!(s-weights!(i-1),i-1))
                             (table!(s,i-1))

def knapsack(size, numItems, values, weights) 

    table = Array.new(size+1) {Array.new(numItems+1) {0}}

    (1...(numItems+1)).each do |i|
        (1...(size+1)).each do |s|
            if (s-weights[i-1]) < 0
                table[s][i] = table[s][i-1]
            else
                table[s][i] = [ values[i-1] + table[s-weights[i-1]][i-1]\
                              , table[s][i-1]].max
            end
        end
    end

    table[size][numItems]

end