sidef-scripts/Math/knapsack_problem_0_1.sf

#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/Knapsack_problem/0-1
#

var raw = <<'TABLE'
map,                      9, 150
compass,                 13,  35
water,                  153, 200
sandwich,                50, 160
glucose,                 15,  60
tin,                     68,  45
banana,                  27,  60
apple,                   39,  40
cheese,                  23,  30
beer,                    52,  10
suntancream,             11,  70
camera,                  32,  30
T-shirt,                 24,  15
trousers,                48,  10
umbrella,                73,  40
waterproof trousers,     42,  70
waterproof overclothes,  43,  75
note-case,               22,  80
sunglasses,               7,  20
towel,                   18,  12
socks,                    4,  50
book,                    30,  10
TABLE

struct KnapsackItem {
    String name,
    Number weight,
    Number value,
}

var items = []
raw.each_line{ |row|
    var fields = row.split(/\s*,\s*/)
    items << KnapsackItem(
          name: fields[0],
        weight: fields[1].to_n,
         value: fields[2].to_n,
    )
}

var max_weight = 400
var p = [
    items.len.of { [[0, []], max_weight.of(nil)...] }...,
    max_weight.inc.of {[0, []]}
]

func optimal(i, w) {
    if (!defined p[i][w]) {
        var item = items[i];
        if (item.weight > w) {
            p[i][w] = optimal(i.dec, w)
        }
        else {
            var x = optimal(i.dec, w)
            var y = optimal(i.dec, w - item.weight)

            if (x[0] > (y[0] + item.value)) {
                p[i][w] = x;
            }
            else {
                p[i][w] = [y[0] + item.value, [y[1]..., item.name]]
            }
        }
    }
    return p[i][w]
}

var sol = optimal(items.end, max_weight)
say "#{sol[0]}: #{sol[1].join(' ')}"