mirror
/
RosettaCodeData
mirror of https://github.com/acmeism/RosettaCodeData.git
1
0
Fork 0
Code Issues Packages Projects Releases Wiki Activity
RosettaCodeData/Task/Knapsack-problem-Unbounded/Phix/knapsack-problem-unbounded....

47 lines
14 KiB
Plaintext
Raw Permalink Blame History

(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>
<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>
<span style="color: #000000;">chosen</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">n</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<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>
<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>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">chosen</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #000000;">profit</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">pitem</span>
<span style="color: #000000;">weight</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">witem</span>
<span style="color: #000000;">volume</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">vitem</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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>
<span style="color: #000080;font-style:italic;">--res is {{profit,(weight left),(space left),{counts}}}</span>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--
Reference in New Issue View Git Blame Copy Permalink