68 lines
19 KiB
Plaintext
68 lines
19 KiB
Plaintext
(phixonline)-->
|
|
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
|
|
<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>
|
|
|
|
<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 weight value pieces</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> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
|
|
<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;">60</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
|
|
<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: #000000;">1</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> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
|
|
<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> <span style="color: #000000;">2</span><span style="color: #0000FF;">}}</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">knapsack</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">max_weight</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">at</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">best_points</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">points</span>
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">best_choices</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">choices</span>
|
|
<span style="color: #004080;">atom</span> <span style="color: #000000;">act_weight</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sub_weight</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">at</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #004080;">integer</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: #000000;">imax</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: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">imax</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">wlim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">max_weight</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">*</span><span style="color: #000000;">witem</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">wlim</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #0000FF;">{</span><span style="color: #000000;">points</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sub_weight</span><span style="color: #0000FF;">,</span><span style="color: #000000;">choices</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;">wlim</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: #000000;">points</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">*</span><span style="color: #000000;">pitem</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">points</span><span style="color: #0000FF;">></span><span style="color: #000000;">best_points</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">best_points</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">points</span>
|
|
<span style="color: #000000;">best_choices</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">choices</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">i</span>
|
|
<span style="color: #000000;">act_weight</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sub_weight</span><span style="color: #0000FF;">+</span><span style="color: #000000;">i</span><span style="color: #0000FF;">*</span><span style="color: #000000;">witem</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>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">best_points</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">act_weight</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">best_choices</span><span style="color: #0000FF;">}</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</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;">400</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: #000080;font-style:italic;">-- {points,act_weight,choices}</span>
|
|
|
|
<span style="color: #004080;">atom</span> <span style="color: #000000;">weight</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">witem</span>
|
|
<span style="color: #004080;">atom</span> <span style="color: #000000;">points</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pitem</span>
|
|
<span style="color: #004080;">string</span> <span style="color: #000000;">idesc</span>
|
|
<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;">goodies</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #0000FF;">{</span><span style="color: #000000;">idesc</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;">i</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;">"%d %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idesc</span><span style="color: #0000FF;">})</span>
|
|
<span style="color: #000000;">weight</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">*</span><span style="color: #000000;">witem</span>
|
|
<span style="color: #000000;">points</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">*</span><span style="color: #000000;">pitem</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>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">points</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: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- sanity check</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;">"Value %d, weight %g [%3.2fs]\n"</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: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
|
|
<!--
|