123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172 |
- #!/usr/bin/ruby
- #
- ## https://rosettacode.org/wiki/Knapsack_problem/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);
- for t in (1..Inf) {
- var item = items[i];
- break if ((w1 = (w - t*item.weight)) < 0)
- break if ((v1 = (v - t*item.volume)) < 0)
- 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
|