Rosetta Code

Knapsack problem/0-1: Difference between revisions

Page Discussion

Knapsack problem/0-1 (view source)

Revision as of 15:33, 22 January 2022

16,465 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring, made p2js compatible
m (→‎{{header|Phix}}: added syntax colouring, made p2js compatible)
Line 5,023:
 
=={{header|Phix}}==
Trivial simplification of the [[Knapsack_problem/Bounded#Phix|Knapsack/Bounded]] solution. SeeBy thatcareful pageordering forwe discussioncan ofensure we find the optimal solution first (see terminate flag).
<!--<lang Phix>(phixonline)-->
In this case I have switched the optimisation on.
<span style="color: #000080;font-style:italic;">-- demo\rosetta\knapsack0.exw</span>
<lang Phix>integer terminate=0
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
 
integer attempts = 0
<span style="color: #004080;">bool</span> <span style="color: #000000;">terminate</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
function knapsack(sequence res, goodies, atom points, weight, at=1, sequence chosen={})
atom {witem,pitem} = goodies[at][2]
<span style="color: #004080;">integer</span> <span style="color: #000000;">attempts</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
integer n = (witem<=weight)
<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;">points</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">weight</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>
chosen &= n
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{?,</span><span style="color: #000000;">witem</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pitem</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>
points += n*pitem -- increase value
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">witem</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
weight -= n*witem -- decrease weight left
<span style="color: #000000;">chosen</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">n</span>
if at=length(goodies) then
<span style="color: #000000;">points</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 value</span>
attempts += 1
<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>
if length(res)=0
<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>
or res<{points,weight} then
<span style="color: #000000;">attempts</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
res = {points,weight,chosen}
<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>
end if
<span style="color: #008080;">or</span> <span style="color: #000000;">res</span><span style="color: #0000FF;"><{</span><span style="color: #000000;">points</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span>
terminate = (n=1)
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">points</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">}</span>
else
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
while n>=0 and not terminate do
<span style="color: #000000;">terminate</span> <span style="color: #0000FF;">=</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: #0000FF;">)</span>
res = knapsack(res,goodies,points,weight,at+1,chosen)
<span style="color: #008080;">else</span>
n -= 1
<span style="color: #000080;font-style:italic;">-- while n&gt;=0 do -- full exhaustive search</span>
chosen[$] = n
<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;">and</span> <span style="color: #008080;">not</span> <span style="color: #000000;">terminate</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- optimised</span>
points -= pitem
<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;">points</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weight</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>
weight += witem
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
end while
<span style="color: #000000;">chosen</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
end if
<span style="color: #000000;">points</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">pitem</span>
return res
<span style="color: #000000;">weight</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">witem</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
function byweightedvalue(object a, b)
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
-- sort by weight/value
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
return compare(a[2][1]/a[2][2],b[2][1]/b[2][2])
-- nb other sort orders break the optimisation
<span style="color: #008080;">function</span> <span style="color: #000000;">byweightedvalue</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #000080;font-style:italic;">-- sort by weight/value</span>
 
<span style="color: #008080;">return</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]/</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">],</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]/</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">])</span>
constant goodies = custom_sort(routine_id("byweightedvalue"),{
<span style="color: #000080;font-style:italic;">-- nb other sort orders break the optimisation</span>
-- item weight value
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
{"map", {9, 150}},
{"compass", {13, 35 }},
<span style="color: #008080;">constant</span> <span style="color: #000000;">goodies</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">byweightedvalue</span><span style="color: #0000FF;">,{</span>
{"water", {153, 200}},
{ <span style="sandwichcolor: #000080;font-style:italic;",>-- item {50, weight 160}},value</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"map"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">150</span><span style="color: #0000FF;">},</span>
{"glucose", {15, 60 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"compass"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">13</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">35</span> <span style="color: #0000FF;">},</span>
{"tin", {68, 45 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"water"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">153</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">200</span><span style="color: #0000FF;">},</span>
{"banana", {27, 60 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"sandwich"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">50</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">160</span><span style="color: #0000FF;">},</span>
{"apple", {39, 40 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"glucose"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">15</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">60</span> <span style="color: #0000FF;">},</span>
{"cheese", {23, 30 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"tin"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">68</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">45</span> <span style="color: #0000FF;">},</span>
{"beer", {52, 10 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"banana"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">27</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">60</span> <span style="color: #0000FF;">},</span>
{"suntan cream", {11, 70 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"apple"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">39</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">40</span> <span style="color: #0000FF;">},</span>
{"camera", {32, 30 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"cheese"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">30</span> <span style="color: #0000FF;">},</span>
{"T-shirt", {24, 15 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"beer"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">52</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span> <span style="color: #0000FF;">},</span>
{"trousers", {48, 10 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"suntan cream"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">70</span> <span style="color: #0000FF;">},</span>
{"umbrella", {73, 40 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"camera"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">30</span> <span style="color: #0000FF;">},</span>
{"waterproof trousers", {42, 70 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"T-shirt"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">24</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">15</span> <span style="color: #0000FF;">},</span>
{"waterproof overclothes", {43, 75 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"trousers"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span> <span style="color: #0000FF;">},</span>
{"note-case", {22, 80 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"umbrella"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">73</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">40</span> <span style="color: #0000FF;">},</span>
{"sunglasses", {7, 20 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"waterproof trousers"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">42</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">70</span> <span style="color: #0000FF;">},</span>
{"towel", {18, 12 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"waterproof overclothes"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">43</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">75</span> <span style="color: #0000FF;">},</span>
{"socks", {4, 50 }},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"note-case"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">22</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">80</span> <span style="color: #0000FF;">},</span>
{"book", {30, 10 }}})
<span style="color: #0000FF;">{</span><span style="color: #008000;">"sunglasses"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">20</span> <span style="color: #0000FF;">},</span>
 
<span style="color: #0000FF;">{</span><span style="color: #008000;">"towel"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12</span> <span style="color: #0000FF;">},</span>
atom t0 = time()
<span style="color: #0000FF;">{</span><span style="color: #008000;">"socks"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">50</span> <span style="color: #0000FF;">},</span>
object {points,weight,counts} = knapsack({},goodies,0,400)
<span style="color: #0000FF;">{</span><span style="color: #008000;">"book"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">30</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span> <span style="color: #0000FF;">}})</span>
printf(1,"Value %d, weight %g [%d attempts, %3.2fs]:\n",{points,400-weight,attempts,time()-t0})
for i=1 to length(counts) do
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
integer c = counts[i]
<span style="color: #004080;">object</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">points</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">,</span><span style="color: #000000;">counts</span><span style="color: #0000FF;">}</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;">400</span><span style="color: #0000FF;">)</span>
if c then
<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;">"Value %d, weight %g [%d attempts, %3.2fs]:\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">points</span><span style="color: #0000FF;">,</span><span style="color: #000000;">400</span><span style="color: #0000FF;">-</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">,</span><span style="color: #000000;">attempts</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
printf(1,"%s\n",{goodies[i][1]})
<span style="color: #008080;">for</span> <span style="color: #000000;">i</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;">counts</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">counts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
end for</lang>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span> <span style="color: #008080;">then</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;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">goodies</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
<pre>
Line 5,109 ⟶ 5,114:
water
</pre>
without the optimisation (ie "and not terminate" removed, full exhaustive search, further lines as above):
<pre>
Value 1030, weight 396 [1216430 attempts, 0.84s]:
Petelomax
7,805

edits

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