# 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);
Inf.times { |t|
var item = items[i];
break if ((w1 = (w - t*item.weight)).is_neg)
break if ((v1 = (v - t*item.volume)).is_neg)

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
``````

#### Output:

``````Max value 54500, with:
Item        Qty     Weight   Vol    Value
--------------------------------------------------
panacea:      9         2   0.225   27000
gold:        11        22   0.022   27500
--------------------------------------------------
Total:                 24   0.247   54500
``````