--
-- demo\rosetta\knapsack.exw
-- =========================
--
integer attempts = 0
function knapsack(sequence res, goodies, atom profit, weight, volume, at=1, sequence chosen={})
    atom {pitem,witem,vitem} = goodies[at][2]
    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
        attempts += 1
        if length(res)=0
        or res<{profit,weight,volume} then
            res = {profit,weight,volume,chosen}
        end if
    else
        while n>=0 do
            res = knapsack(res,goodies,profit,weight,volume,at+1,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
{"panacea",      {3000,   0.3, 0.025}},
{"ichor",        {1800,   0.2, 0.015}},
{"shiney shiney",{2500,   2.0, 0.002}}}

sequence res -- {profit,(weight left),(space left),{counts}}
res = knapsack({},goodies,0,25,0.25)
integer {p,i,g} = res[4]
sequence {d,pwv} = columnize(goodies),
         {?,w,v} = columnize(pwv)
atom weight = sum(sq_mul(res[4],w)),
     volume = sum(sq_mul(res[4],v))
printf(1,"Profit %d: %d %s, %d %s, %d %s\n",
        {res[1],p,d[1],i,d[2],g,d[3]})
printf(1," [weight:%g, volume:%g, %d attempts]\n",
        {weight,volume,attempts})