V items = [
   ‘sandwich’     = (50, 60, 2),
   ‘map’          = (9, 150, 1),
   ‘compass’      = (13, 35, 1),
   ‘water’        = (153, 200, 3),
   ‘glucose’      = (15, 60, 2),
   ‘tin’          = (68, 45, 3),
   ‘banana’       = (27, 60, 3),
   ‘apple’        = (39, 40, 3),
   ‘cheese’       = (23, 30, 1),
   ‘beer’         = (52, 10, 3),
   ‘suntan cream’ = (11, 70, 1),
   ‘camera’       = (32, 30, 1),
   ‘t-shirt’      = (24, 15, 2),
   ‘trousers’     = (48, 10, 2),
   ‘umbrella’     = (73, 40, 1),
   ‘w-trousers’   = (42, 70, 1),
   ‘w-overcoat’   = (43, 75, 1),
   ‘note-case’    = (22, 80, 1),
   ‘sunglasses’   = (7, 20, 1),
   ‘towel’        = (18, 12, 2),
   ‘socks’        = (4, 50, 1),
   ‘book’         = (30, 10, 2)
]

V item_keys = items.keys()

[(Int, Int) = (Int, [(Int, String)])] cache

F choose_item(weight, idx)
   [(Int, String)] best_list
   I idx < 0
      R (0, best_list)
   V k = (weight, idx)
   V? c = :cache.find(k)
   I c != N
      R c
   V name = :item_keys[idx]
   V (w, v, qty) = :items[name]
   V best_v = 0

   L(i) 0..qty
      V wlim = weight - i * w
      I wlim < 0
         L.break
      V (val, taken) = choose_item(wlim, idx - 1)
      I val + i * v > best_v
         best_v = val + i * v
         best_list = copy(taken)
         best_list.append((i, name))
   :cache[k] = (best_v, best_list)
   R (best_v, best_list)

V (v, lst) = choose_item(400, items.len - 1)
V w = 0
L(cnt, name) lst
   I cnt > 0
      print(cnt‘ ’name)
      w += items[name][0] * cnt

print(‘Total weight: ’w‘ Value: ’v)