Rosetta Code

Knapsack problem/Unbounded: Difference between revisions

Page Discussion

Knapsack problem/Unbounded (view source)

Revision as of 16:13, 23 January 2022

12,830 bytes added ,  2 years ago
m
→‎{{header|Phix}}: show all four solns, added syntax colouring, marked p2js compatible
(→‎{{header|Wren}}: Now uses new core library method.)
m (→‎{{header|Phix}}: show all four solns, added syntax colouring, marked p2js compatible)
Line 2,788:
For each goodie, fill yer boots, then (except for the last) recursively try with fewer and fewer.<br>
Increase profit and decrease weight/volume to pick largest profit for least weight and space.
<!--<lang Phix>(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\knapsack.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
-- =========================
<span style="color: #008080;">function</span> <span style="color: #000000;">knapsack</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">goodies</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">profit</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">weight</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">volume</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">at</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">={})</span>
--
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{?,</span><span style="color: #000000;">pitem</span><span style="color: #0000FF;">,</span><span style="color: #000000;">witem</span><span style="color: #0000FF;">,</span><span style="color: #000000;">vitem</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">goodies</span><span style="color: #0000FF;">[</span><span style="color: #000000;">at</span><span style="color: #0000FF;">]</span>
integer attempts = 0
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">/</span><span style="color: #000000;">witem</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">volume</span><span style="color: #0000FF;">/</span><span style="color: #000000;">vitem</span><span style="color: #0000FF;">))</span>
function knapsack(sequence res, goodies, atom profit, weight, volume, at=1, sequence chosen={})
<span style="color: #000000;">chosen</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">n</span>
atom {pitem,witem,vitem} = goodies[at][2]
<span style="color: #000000;">profit</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">pitem</span> <span style="color: #000080;font-style:italic;">-- increase profit</span>
integer n = min(floor(weight/witem),floor(volume/vitem))
<span style="color: #000000;">weight</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">witem</span> <span style="color: #000080;font-style:italic;">-- decrease weight left</span>
chosen &= n
<span style="color: #000000;">volume</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">vitem</span> <span style="color: #000080;font-style:italic;">-- decrease space left</span>
profit += n*pitem -- increase profit
<span style="color: #008080;">if</span> <span style="color: #000000;">at</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">goodies</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
weight -= n*witem -- decrease weight left
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pwvc</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">profit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">,</span><span style="color: #000000;">volume</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">}</span>
volume -= n*vitem -- decrease space left
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">profit</span><span style="color: #0000FF;">></span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
if at=length(goodies) then
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">pwvc</span><span style="color: #0000FF;">}</span>
attempts += 1
<span style="color: #008080;">elsif</span> <span style="color: #000000;">profit</span><span style="color: #0000FF;">=</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
if length(res)=0
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pwvc</span><span style="color: #0000FF;">)</span>
or res<{profit,weight,volume} then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
res = {profit,weight,volume,chosen}
<span style="color: #008080;">else</span>
end if
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
else
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">knapsack</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">goodies</span><span style="color: #0000FF;">,</span><span style="color: #000000;">profit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">,</span><span style="color: #000000;">volume</span><span style="color: #0000FF;">,</span><span style="color: #000000;">at</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">))</span>
while n>=0 do
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
res = knapsack(res,goodies,profit,weight,volume,at+1,chosen)
<span style="color: #000000;">chosen</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
n -= 1
<span style="color: #000000;">profit</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">pitem</span>
chosen[$] = n
<span style="color: #000000;">weight</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">witem</span>
profit -= pitem
<span style="color: #000000;">volume</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">vitem</span>
weight += witem
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
volume += vitem
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end while
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
return res
end function
<span style="color: #008080;">constant</span> <span style="color: #000000;">goodies</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000080;font-style:italic;">-- item profit weight volume</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"ichor"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1800</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.015</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"panacea"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3000</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.025</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"shiney shiney"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2500</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2.0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.002</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">descs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">profits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">wts</span><span style="color: #0000FF;">,</span><span style="color: #000000;">vols</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">(</span><span style="color: #000000;">goodies</span><span style="color: #0000FF;">)</span>
sequence <span resstyle="color: #000080;font-style:italic;">--res is {{profit,(weight left),(space left),{counts}}}</span>▼
constant goodies = {
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">knapsack</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">goodies</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0.25</span><span style="color: #0000FF;">)</span>
-- item profit weight volume
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
{"panacea", {3000, 0.3, 0.025}},
<span style="color: #004080;">integer</span> <span style="color: #000000;">profit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
{"ichor", {1800, 0.2, 0.015}},
<span style="color: #004080;">sequence</span> <span style="color: #000000;">counts</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]</span>
{"shiney shiney",{2500, 2.0, 0.002}}}
<span style="color: #004080;">atom</span> <span style="color: #000000;">weight</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">counts</span><span style="color: #0000FF;">,</span><span style="color: #000000;">wts</span><span style="color: #0000FF;">)),</span> <span style="color: #000000;">volume</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">counts</span><span style="color: #0000FF;">,</span><span style="color: #000000;">vols</span><span style="color: #0000FF;">))</span>
 
<span style="color: #004080;">string</span> <span style="color: #000000;">what</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"%2d %s"</span><span style="color: #0000FF;">},</span><span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">({</span><span style="color: #000000;">counts</span><span style="color: #0000FF;">,</span><span style="color: #000000;">descs</span><span style="color: #0000FF;">})}),</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)</span>
▲sequence res -- {profit,(weight left),(space left),{counts}}
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Profit %d: %s [weight:%.1f, volume:%g]\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">profit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">what</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">,</span><span style="color: #000000;">volume</span><span style="color: #0000FF;">})</span>
res = knapsack({},goodies,0,25,0.25)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
integer {p,i,g} = res[4]
<!--</lang>-->
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})</lang>
{{out}}
<pre>
Profit 54500: 915 panaceaichor, 0 ichorpanacea, 11 shiney shiney [weight:25.0, volume:0.247]
Profit 54500: 10 ichor, 3 panacea, 11 shiney shiney [weight:24.79, volume:0.247, 98 attempts]
Profit 54500: 5 ichor, 6 panacea, 11 shiney shiney [weight:24.8, volume:0.247]
Profit 54500: 0 ichor, 9 panacea, 11 shiney shiney [weight:24.7, volume:0.247]
</pre>
You get the same result whatever order the goodies are in, but with a different number of attempts, gold/ichor/panacea being the
highest at 204.
 
=={{header|PicoLisp}}==
Petelomax
7,813

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/89798"