62 lines
1.6 KiB
Text
62 lines
1.6 KiB
Text
|
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)
|