68 lines
1.6 KiB
Plaintext
68 lines
1.6 KiB
Plaintext
var raw = <<'TABLE'
|
|
map 9 150 1
|
|
compass 13 35 1
|
|
water 153 200 2
|
|
sandwich 50 60 2
|
|
glucose 15 60 2
|
|
tin 68 45 3
|
|
banana 27 60 3
|
|
apple 39 40 3
|
|
cheese 23 30 1
|
|
beer 52 10 1
|
|
suntancream 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
|
|
TABLE
|
|
|
|
struct KnapsackItem {
|
|
String name,
|
|
Number weight,
|
|
Number value,
|
|
Number quant,
|
|
}
|
|
|
|
var items = []
|
|
raw.each_line{ |row|
|
|
var fields = row.words;
|
|
items << KnapsackItem(
|
|
name: fields[0],
|
|
weight: fields[1].to_n,
|
|
value: fields[2].to_n,
|
|
quant: fields[3].to_n,
|
|
)
|
|
}
|
|
|
|
func pick(weight, pos) is cached {
|
|
|
|
if (pos.is_neg || weight.is_neg || weight.is_zero) {
|
|
return (0, 0, [])
|
|
}
|
|
|
|
var (bv=0, bi=0, bw=0, bp=[])
|
|
var item = items[pos];
|
|
|
|
for i in range(0, item.quant) {
|
|
break if (i*item.weight > weight)
|
|
var (v, w, p) = pick(weight - i*item.weight, pos.dec)
|
|
next if ((v += i*item.value) <= bv)
|
|
(bv, bi, bw, bp) = (v, i, w, p)
|
|
}
|
|
|
|
(bv, bw + bi*item.weight, [bp..., bi])
|
|
}
|
|
|
|
var (v, w, p) = pick(400, items.end)
|
|
p.range.each { |i|
|
|
say "#{p[i]} of #{items[i].name}" if p[i].is_pos
|
|
}
|
|
say "Value: #{v}; Weight: #{w}"
|