71 lines
1.7 KiB
Plaintext
71 lines
1.7 KiB
Plaintext
var raw = <<'TABLE'
|
|
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
|
|
suntancream, 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
|
|
TABLE
|
|
|
|
struct KnapsackItem {
|
|
String name,
|
|
Number weight,
|
|
Number value,
|
|
}
|
|
|
|
var items = []
|
|
raw.each_line{ |row|
|
|
var fields = row.split(/\s*,\s*/)
|
|
items << KnapsackItem(
|
|
name: fields[0],
|
|
weight: fields[1].to_n,
|
|
value: fields[2].to_n,
|
|
)
|
|
}
|
|
|
|
var max_weight = 400
|
|
var p = [
|
|
items.len.of { [[0, []], max_weight.of(nil)...] }...,
|
|
max_weight.inc.of {[0, []]}
|
|
]
|
|
|
|
func optimal(i, w) {
|
|
if (!defined p[i][w]) {
|
|
var item = items[i];
|
|
if (item.weight > w) {
|
|
p[i][w] = optimal(i.dec, w)
|
|
}
|
|
else {
|
|
var x = optimal(i.dec, w)
|
|
var y = optimal(i.dec, w - item.weight)
|
|
|
|
if (x[0] > (y[0] + item.value)) {
|
|
p[i][w] = x;
|
|
}
|
|
else {
|
|
p[i][w] = [y[0] + item.value, [y[1]..., item.name]]
|
|
}
|
|
}
|
|
}
|
|
return p[i][w]
|
|
}
|
|
|
|
var sol = optimal(items.end, max_weight)
|
|
say "#{sol[0]}: #{sol[1]}"
|