knapsack[values, weights, capacity] :=
{
   n = length[values]

   if length[weights] != n
   {
      println["knapsack:  length of values does not equal length of weights."]
      return undef
   }

   V = new array[[n+1, capacity+1], 0]
   keep = new array[[n+1, capacity+1], false]

   for i = 1 to n
   {
      for w = 0 to capacity
      {
         if weights@(i-1) <= w and (values@(i-1) + V@(i-1)@(w - weights@(i-1)) > V@(i-1)@w)
         {
            V@i@w = values@(i-1) + V@(i-1)@(w-weights@(i-1))
            keep@i@w = true
         } else
         {
            V@i@w = V@(i-1)@w
            keep@i@w = false
         }
      }
   }

   included = new array
   K = capacity
   for i = n to 1 step -1
      if keep@i@K == true
      {
         included.push[ [i-1, values@(i-1), weights@(i-1)] ]
         K = K - weights@(i-1)
      }

   return concat[V@n@capacity, included.transpose[]]
}

i= [["map",                      9,   150],
    ["compass",                 13,    35],
    ["water",                  153,   200],
    ["sandwich",                50,   160],
    ["glucose",                 15,    60],
    ["tin",                     68,    45],
    ["banana",                  27,    60],
    ["apple",                   39,    40],
    ["cheese",                  23,    30],
    ["beer",                    52,    10],
    ["suntan cream",            11,    70],
    ["camera",                  32,    30],
    ["T-shirt",                 24,    15],
    ["trousers",                48,    10],
    ["umbrella",                73,    40],
    ["waterproof trousers",     42,    70],
    ["waterproof overclothes",  43,    75],
    ["note-case",               22,    80],
    ["sunglasses",               7,    20],
    ["towel",                   18,    12],
    ["socks",                    4,    50],
    ["book",                    30,    10]]

[maxval, indices, values, weights] = knapsack[i.getColumn[2], i.getColumn[1], 400]
println["Items:"]

for ind = sort[indices]
   println["   " +i@ind@0]

println[]
println["Total weight: " + sum[weights]]
println["Total value:  $maxval"]