sidef/scripts/Expensive/knapsack_problem_unbounded.sf

#!/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