42 lines
1.5 KiB
Text
42 lines
1.5 KiB
Text
F totalvalue(comb)
|
||
V totwt = 0
|
||
V totval = 0
|
||
L(item, wt, val) comb
|
||
totwt += wt
|
||
totval += val
|
||
R I totwt <= 400 {(totval, -totwt)} E (0, 0)
|
||
|
||
V items = [
|
||
(‘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)
|
||
]
|
||
|
||
F knapsack01_dp(items, limit)
|
||
V table = [[0] * (limit + 1)] * (items.len + 1)
|
||
|
||
L(j) 1 .. items.len
|
||
V (item, wt, val) = items[j - 1]
|
||
L(w) 1 .. limit
|
||
I wt > w
|
||
table[j][w] = table[j - 1][w]
|
||
E
|
||
table[j][w] = max(table[j - 1][w], table[j - 1][w - wt] + val)
|
||
|
||
[(String, Int, Int)] result
|
||
V w = limit
|
||
L(j) (items.len .< 0).step(-1)
|
||
I table[j][w] != table[j - 1][w]
|
||
V (item, wt, val) = items[j - 1]
|
||
result.append(items[j - 1])
|
||
w -= wt
|
||
R result
|
||
|
||
V bagged = knapsack01_dp(items, 400)
|
||
print("Bagged the following items\n "sorted(bagged.map((item, _, _2) -> item)).join("\n "))
|
||
V (val, wt) = totalvalue(bagged)
|
||
print(‘for a total value of #. and a total weight of #.’.format(val, -wt))
|