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

#### Output:

``````1 of map
1 of compass
1 of water
2 of glucose
3 of banana
1 of cheese
1 of suntancream
1 of w_overcoat
1 of note-case
1 of sunglasses
1 of socks
Value: 1010; Weight: 396
``````