Unbounded
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
Output:
Max value 54500, with:
Item Qty Weight Vol Value
--------------------------------------------------
panacea: 9 2 0.225 27000
gold: 11 22 0.022 27500
--------------------------------------------------
Total: 24 0.247 54500
Last updated