(phixonline)-->
-- demo\rosetta\knapsack.exw
with javascript_semantics
function knapsack(sequence res, goodies, atom profit, weight, volume, at=1, sequence chosen={})
atom {?,pitem,witem,vitem} = goodies[at]
integer n = min(floor(weight/witem),floor(volume/vitem))
chosen &= n
profit += n*pitem -- increase profit
weight -= n*witem -- decrease weight left
volume -= n*vitem -- decrease space left
if at=length(goodies) then
sequence pwvc = {profit,weight,volume,chosen}
if length(res)=0 or profit>res[1][1] then
res = {pwvc}
elsif profit=res[1][1] then
res = append(res,pwvc)
end if
else
while n>=0 do
res = knapsack(res,goodies,profit,weight,volume,at+1,deep_copy(chosen))
n -= 1
chosen[$] = n
profit -= pitem
weight += witem
volume += vitem
end while
end if
return res
end function
constant goodies = {-- item profit weight volume
{"ichor", 1800, 0.2, 0.015},
{"panacea", 3000, 0.3, 0.025},
{"shiney shiney", 2500, 2.0, 0.002}},
{descs,profits,wts,vols} = columnize(goodies)
--res is {{profit,(weight left),(space left),{counts}}}
sequence res = knapsack({},goodies,0,25,0.25)
for r=1 to length(res) do
integer profit = res[r][1]
sequence counts = res[r][4]
atom weight = sum(sq_mul(counts,wts)), volume = sum(sq_mul(counts,vols))
string what = join(apply(true,sprintf,{{"%2d %s"},columnize({counts,descs})}),", ")
printf(1,"Profit %d: %s [weight:%.1f, volume:%g]\n",{profit,what,weight,volume})
end for