49 lines
1.5 KiB
Plaintext
49 lines
1.5 KiB
Plaintext
--
|
|
-- 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})
|