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