66 lines
1.3 KiB
Plaintext
66 lines
1.3 KiB
Plaintext
struct KnapsackItem {
|
|
Number volume,
|
|
Number weight,
|
|
Number value,
|
|
String name,
|
|
}
|
|
|
|
var items = [
|
|
KnapsackItem(25, 3, 3000, "panacea")
|
|
KnapsackItem(15, 2, 1800, "ichor" )
|
|
KnapsackItem( 2, 20, 2500, "gold" )
|
|
]
|
|
|
|
var (
|
|
max_weight = 250,
|
|
max_vol = 250,
|
|
vsc = 1000,
|
|
wsc = 10
|
|
)
|
|
|
|
func solve(i, w, v) is cached {
|
|
return [0, []] if i.is_neg;
|
|
|
|
var x = solve(i.dec, w, v);
|
|
|
|
var (w1, v1);
|
|
Inf.times { |t|
|
|
var item = items[i];
|
|
break if ((w1 = (w - t*item.weight)).is_neg)
|
|
break if ((v1 = (v - t*item.volume)).is_neg)
|
|
|
|
var y = solve(i.dec, w1, v1);
|
|
if ((var tmp = (y[0] + t*item.value)) > x[0]) {
|
|
x = [tmp, [y[1]..., [i, t]]];
|
|
}
|
|
}
|
|
|
|
return x
|
|
}
|
|
|
|
var x = solve(items.end, max_weight, max_vol)
|
|
|
|
print <<"EOT"
|
|
Max value #{x[0]}, with:
|
|
Item Qty Weight Vol Value
|
|
#{"-" * 50}
|
|
EOT
|
|
|
|
var (wtot=0, vtot=0);
|
|
x[1].each { |s|
|
|
var item = items[s[0]];
|
|
" #{item.name}:\t% 3d % 8d% 8g% 8d\n".printf(
|
|
s[1],
|
|
item.weight * s[1] / wsc,
|
|
item.volume * s[1] / vsc,
|
|
item.value * s[1]
|
|
);
|
|
wtot += (item.weight * s[1]);
|
|
vtot += (item.volume * s[1]);
|
|
}
|
|
|
|
print <<"EOT"
|
|
#{"-" * 50}
|
|
Total:\t #{"%8d%8g%8d" % (wtot/wsc, vtot/vsc, x[0])}
|
|
EOT
|