sidef/scripts/Expensive/knapsack_problem_bounded.sf

#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/Knapsack_problem/Bounded
#

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}"