Knapsack problem/Unbounded: Difference between revisions

Content added Content deleted
(Whole Scala contribution erased without a reason.)
(Undo revision 263806 by Cloudius (talk)Roll back all but Scala updates for reason given in last rollback)
Line 1: Line 1:
{{task|Classic CS problems and programs}}
{{task|Classic CS problems and programs}}


A traveler gets diverted and has to make an unscheduled stop in what turns out to be Shangri La. Opting to leave, she or he is allowed to take as much as the liked items following, so long as it will fit in his knapsack, and can carry it.
A traveler gets diverted and has to make an unscheduled stop in what turns out to be Shangri La.   Opting to leave, he is allowed to take as much as he likes of the following items, so long as it will fit in his knapsack, and he can carry it.


The traveler knows that no more than 25 'weights' in total can be carried; and that the capacity of the knapsack is 0.25 'cubic lengths'.
He knows that he can carry no more than   25   'weights' in total;   and that the capacity of his knapsack is   0.25   'cubic lengths'.


Looking just above the bar codes on the items their weights and volumes are found. Be digging out the recent copy of a financial paper the value of each item can be get.
Looking just above the bar codes on the items he finds their weights and volumes.   He digs out his recent copy of a financial paper and gets the value of each item.
<table
<table style="text-align: left; width: 80%;" border="4" cellpadding="2" cellspacing="2"><tr>
<td style="font-weight: bold;" align="left" nowrap="nowrap" valign="middle">Item</td>
style="text-align: left; width: 80%;" border="4"
cellpadding="2" cellspacing="2"><tr><td
<td style="font-weight: bold;" align="left" nowrap="nowrap" valign="middle">Explanation</td>
<td style="font-weight: bold;" align="right" nowrap="nowrap" valign="middle">Value (each)</td>
style="font-weight: bold;" align="left" nowrap="nowrap"
<td style="font-weight: bold;" align="right" nowrap="nowrap" valign="middle">weight</td>
valign="middle">Item</td><td
<td style="font-weight: bold;" align="right" nowrap="nowrap" valign="middle">Volume (each)</td>
style="font-weight: bold;" align="left" nowrap="nowrap"
valign="middle">Explanation</td><td
</tr><tr>
<td align="left" nowrap="nowrap" valign="middle">panacea (vials of)</td>
style="font-weight: bold;" align="left" nowrap="nowrap"
<td align="left" nowrap="nowrap" valign="middle">Incredible healing properties</td>
valign="middle">Value (each)</td><td
<td align="left" align="right" nowrap="nowrap" valign="middle">3000</td>
style="font-weight: bold;" align="left" nowrap="nowrap"
<td align="left" align="right" nowrap="nowrap" valign="middle">0.3</td>
valign="middle">weight</td><td
<td align="left" align="right" nowrap="nowrap" valign="middle">0.025</td>
style="font-weight: bold;" align="left" nowrap="nowrap"
valign="middle">Volume (each)</td></tr><tr><td
</tr><tr>
<td align="left" nowrap="nowrap" valign="middle">ichor (ampules of)</td>
align="left" nowrap="nowrap" valign="middle">panacea
<td align="left" nowrap="nowrap" valign="middle">Vampires blood</td>
(vials of)</td><td align="left" nowrap="nowrap"
<td align="left" align="right" nowrap="nowrap" valign="middle">1800</td>
valign="middle">Incredible healing properties</td><td
<td align="left" align="right" nowrap="nowrap" valign="middle">0.2</td>
align="left" nowrap="nowrap" valign="middle">3000</td><td
<td align="left" align="right" nowrap="nowrap" valign="middle">0.015</td>
align="left" nowrap="nowrap" valign="middle">0.3</td><td
align="left" nowrap="nowrap" valign="middle">0.025</td></tr><tr><td
</tr><tr>
<td align="left" nowrap="nowrap" valign="middle">gold (bars)</td>
align="left" nowrap="nowrap" valign="middle">ichor
<td align="left" nowrap="nowrap" valign="middle">Shiney shiney</td>
(ampules of)</td><td align="left" nowrap="nowrap"
<td align="left" align="right" nowrap="nowrap" valign="middle">2500</td>
valign="middle">Vampires blood</td><td align="left"
<td align="left" align="right" nowrap="nowrap" valign="middle">2.0</td>
nowrap="nowrap" valign="middle">1800</td><td
<td align="left" align="right" nowrap="nowrap" valign="middle">0.002</td>
align="left" nowrap="nowrap" valign="middle">0.2</td><td
align="left" nowrap="nowrap" valign="middle">0.015</td></tr><tr><td
</tr><tr>
<td style="background-color: rgb(255, 204, 255);" align="left" nowrap="nowrap" valign="middle">Knapsack</td>
align="left" nowrap="nowrap" valign="middle">gold
<td style="background-color: rgb(255, 204, 255);" align="left" nowrap="nowrap" valign="middle">For the carrying of</td>
(bars)</td><td align="left" nowrap="nowrap"
valign="middle">Shiney shiney</td><td align="left"
<td style="background-color: rgb(255, 204, 255);" align="right" nowrap="nowrap" valign="middle">-</td>
<td style="background-color: rgb(255, 204, 255);" align="right" nowrap="nowrap" valign="middle">&lt;=25</td>
nowrap="nowrap" valign="middle">2500</td><td
<td style="background-color: rgb(255, 204, 255);" align="right" nowrap="nowrap" valign="middle">&lt;=0.25</td>
align="left" nowrap="nowrap" valign="middle">2.0</td><td
align="left" nowrap="nowrap" valign="middle">0.002</td></tr><tr><td
</tr></table>
style="background-color: rgb(255, 204, 255);" align="left"
nowrap="nowrap" valign="middle">Knapsack</td><td
style="background-color: rgb(255, 204, 255);" align="left"
nowrap="nowrap" valign="middle">For the carrying of</td><td
style="background-color: rgb(255, 204, 255);" align="left"
nowrap="nowrap" valign="middle">-</td><td
style="background-color: rgb(255, 204, 255);" align="left"
nowrap="nowrap" valign="middle">&lt;=25</td><td
style="background-color: rgb(255, 204, 255);" align="left"
nowrap="nowrap" valign="middle">&lt;=0.25&nbsp;</td></tr>
</table>


<br>
<br>
The traveller can only take whole units of any item, but there is much more of any item than ever could be carried.
He can only take whole units of any item, but there is much more of any item than he could ever carry


;Task:
;Task:
Show how many of each item the traveller can take to maximize the value of items is carried away.
Show how many of each item does he take to maximize the value of items he is carrying away with him.


;Note:
;Note:
* There are four solutions that maximize the value taken. Only one ''need'' be given.
* &nbsp; There are four solutions that maximize the value taken. &nbsp; Only one ''need'' be given.


<!-- All solutions
<!-- All solutions

# ((value, -weight, -volume), (#panacea, #ichor, #gold)
# ((value, -weight, -volume), (#panacea, #ichor, #gold)
[((54500, -25.0, -0.24699999999999997), (0, 15, 11)),
[((54500, -25.0, -0.24699999999999997), (0, 15, 11)),
Line 53: Line 71:
# (9, 0, 11) also minimizes weight and volume within the limits of calculation
# (9, 0, 11) also minimizes weight and volume within the limits of calculation
-->
-->

;Related tasks:
;Related tasks:
* [[Knapsack problem/Bounded]]
* &nbsp; [[Knapsack problem/Bounded]]
* [[Knapsack problem/Continuous]]
* &nbsp; [[Knapsack problem/Continuous]]
* [[Knapsack problem/0-1]]<br><br>
* &nbsp; [[Knapsack problem/0-1]]
<br><br>

=={{header|360 Assembly}}==
=={{header|360 Assembly}}==
{{trans|Visual Basic}}
{{trans|Visual Basic}}
Line 258: Line 279:
END KNAPSACK</lang>
END KNAPSACK</lang>
{{out}}
{{out}}
<pre>
<pre> Value Weight Volume Panacea Ichor Gold
Value Weight Volume Panacea Ichor Gold
54500 24.7 0.247 9 0 11
54500 24.7 0.247 9 0 11
54500 24.8 0.247 6 5 11
54500 24.8 0.247 6 5 11
Line 264: Line 286:
54500 25.0 0.247 0 15 11
54500 25.0 0.247 0 15 11
</pre>
</pre>

=={{header|Ada}}==
=={{header|Ada}}==
{{output?|Ada|reason}}
{{trans|Python}}
{{trans|Python}}
<lang Ada>with Ada.Text_IO;
<lang Ada>with Ada.Text_IO;
Line 332: Line 354:
Ada.Text_IO.Put_Line ("Gold: " & Natural'Image (Best_Amounts (3)));
Ada.Text_IO.Put_Line ("Gold: " & Natural'Image (Best_Amounts (3)));
end Knapsack_Unbounded;</lang>
end Knapsack_Unbounded;</lang>

=={{header|ALGOL 68}}==
=={{header|ALGOL 68}}==
{{trans|Python}}<lang algol68>MODE BOUNTY = STRUCT(STRING name, INT value, weight, volume);
{{trans|Python}}<lang algol68>MODE BOUNTY = STRUCT(STRING name, INT value, weight, volume);
Line 442: Line 465:
name OF items, max items));
name OF items, max items));
printf(($" The weight to carry is "f(d)", and the volume used is "f(d)l$,
printf(($" The weight to carry is "f(d)", and the volume used is "f(d)l$,
weight OF max, volume OF max))</lang>
weight OF max, volume OF max))</lang>Output:
Output:<pre>The maximum value achievable (by dynamic programming) is +54500
<pre>The maximum value achievable (by dynamic programming) is +54500
The number of (panacea, ichor, gold) items to achieve this is: ( 9, 0, 11) respectively
The number of (panacea, ichor, gold) items to achieve this is: ( 9, 0, 11) respectively
The weight to carry is 247, and the volume used is 247</pre>
The weight to carry is 247, and the volume used is 247</pre>

=={{header|AutoHotkey}}==
=={{header|AutoHotkey}}==
{{output?|AutoHotkey|reason}}
Brute Force.
Brute Force.
<lang AutoHotkey>Item = Panacea,Ichor,Gold
<lang AutoHotkey>Item = Panacea,Ichor,Gold
Line 474: Line 497:
}
}
MsgBox Value = %$%`n`nPanacea`tIchor`tGold`tWeight`tVolume`n%t%</lang>
MsgBox Value = %$%`n`nPanacea`tIchor`tGold`tWeight`tVolume`n%t%</lang>

=={{header|Bracmat}}==
=={{header|Bracmat}}==
<lang bracmat>(knapsack=
<lang bracmat>(knapsack=
Line 546: Line 570:
!knapsack;
!knapsack;
</lang>
</lang>
Output:
Output:<pre>Take 15 items of ichor.
<pre>Take 15 items of ichor.
Finally take 11 items of gold.
Finally take 11 items of gold.
The value in the knapsack is 54500.</pre>
The value in the knapsack is 54500.</pre>

=={{header|C}}==
=={{header|C}}==

figures out the best (highest value) set by brute forcing every possible subset.
figures out the best (highest value) set by brute forcing every possible subset.

<lang c>#include <stdio.h>
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
Line 610: Line 638:
}
}
</lang>
</lang>

{{output}}<pre>9 panacea
{{output}}<pre>9 panacea
0 ichor
0 ichor
11 gold
11 gold
best value: 54500</pre>
best value: 54500
</pre>

=={{header|C_sharp|C#}}==
=={{header|C_sharp|C#}}==
<lang csharp>/*Knapsack
<lang csharp>/*Knapsack
Line 670: Line 701:
}
}
}</lang>
}</lang>
Produces:
Produces:<pre>===Solver Foundation Service Report===
<pre>
===Solver Foundation Service Report===
Date: 28/01/2012 17:18:56
Date: 28/01/2012 17:18:56
Version: Microsoft Solver Foundation 3.0.1.10599 Express Edition
Version: Microsoft Solver Foundation 3.0.1.10599 Express Edition
Line 704: Line 737:
take(Panacea): 9
take(Panacea): 9
take(Ichor): 0
take(Ichor): 0
take(Gold): 11</pre>
take(Gold): 11
</pre>

=={{header|Clojure}}==
=={{header|Clojure}}==
<lang lisp>(defstruct item :value :weight :volume)
<lang lisp>(defstruct item :value :weight :volume)
Line 746: Line 781:
(println "Total volume: " (float v))
(println "Total volume: " (float v))
(println "Containing: " p "Panacea," i "Ichor," g "Gold")))</lang>
(println "Containing: " p "Panacea," i "Ichor," g "Gold")))</lang>
Calling <tt>(print-knapsack (best-by-value (knapsacks)))</tt> would result in something like:<pre>Maximum value: 54500
Calling <tt>(print-knapsack (best-by-value (knapsacks)))</tt> would result in something like:
<pre>Maximum value: 54500
Total weight: 24.7
Total weight: 24.7
Total volume: 0.247
Total volume: 0.247
Line 759: Line 795:
(print-knapsack k)
(print-knapsack k)
(println)))</lang>
(println)))</lang>
Calling <tt>(print-knapsacks (all-best-by-value (knapsacks)))</tt> would result in something like:<pre>Maximum value: 54500.0
Calling <tt>(print-knapsacks (all-best-by-value (knapsacks)))</tt> would result in something like:
<pre>
Maximum value: 54500.0
Total weight: 25.0
Total weight: 25.0
Total volume: 0.247
Total volume: 0.247
Line 777: Line 815:
Total weight: 24.7
Total weight: 24.7
Total volume: 0.247
Total volume: 0.247
Containing: 9 Panacea, 0 Ichor, 11 Gold</pre>
Containing: 9 Panacea, 0 Ichor, 11 Gold
</pre>

=={{header|Common Lisp}}==
=={{header|Common Lisp}}==
A dynamic programming <i>O(maxVolume &times; maxWeight &times; nItems)</i> solution, where volumes and weights are integral values.
A dynamic programming <i>O(maxVolume &times; maxWeight &times; nItems)</i> solution, where volumes and weights are integral values.
Line 842: Line 882:
250 ; total volume
250 ; total volume
247) ; total weight</pre>
247) ; total weight</pre>

=={{header|D}}==
=={{header|D}}==
{{trans|Python}}
{{trans|Python}}
Line 899: Line 940:
This is achieved by carrying (one solution) 0 panacea, 15 ichor and 11 gold
This is achieved by carrying (one solution) 0 panacea, 15 ichor and 11 gold
The weight to carry is 25.0 and the volume used is 0.247</pre>
The weight to carry is 25.0 and the volume used is 0.247</pre>

===Alternative Version===
===Alternative Version===
The output is the same.
The output is the same.
Line 927: Line 969:
writefln("The weight to carry is %4.1f and the volume used is %5.3f", best[0][1..$]);
writefln("The weight to carry is %4.1f and the volume used is %5.3f", best[0][1..$]);
}</lang>
}</lang>

=={{header|E}}==
=={{header|E}}==
{{output?|E|reason}}
This is a mostly brute-force general solution (the first author of this example does not know dynamic programming); the only optimization is that when considering the last (third) treasure type, it does not bother filling with anything but the maximum amount.
This is a mostly brute-force general solution (the first author of this example does not know dynamic programming); the only optimization is that when considering the last (third) treasure type, it does not bother filling with anything but the maximum amount.
<lang e>pragma.enable("accumulator")
<lang e>pragma.enable("accumulator")
Line 1,010: Line 1,052:


printBest(emptyKnapsack, [panacea, ichor, gold])</lang>
printBest(emptyKnapsack, [panacea, ichor, gold])</lang>

=={{header|EchoLisp}}==
=={{header|EchoLisp}}==
Use a cache, and multiply by 10^n to get an integer problem.
Use a cache, and multiply by 10^n to get an integer problem.
Line 1,082: Line 1,125:


(length (hash-keys H)) ;; # entries in cache
(length (hash-keys H)) ;; # entries in cache
→ 218</lang>
→ 218

</lang>

=={{header|Eiffel}}==
=={{header|Eiffel}}==
<lang Eiffel>
<lang Eiffel>
Line 1,166: Line 1,212:
end
end


end</lang>
end
</lang>
{{out}}
{{out}}
<pre>
<pre>Maximum value achievable is 54500.
Maximum value achievable is 54500.
This is achieved by carrying 0 panacea, 15 ichor and 11 gold.
This is achieved by carrying 0 panacea, 15 ichor and 11 gold.
The weight is 25 and the volume is 0.247.
The weight is 25 and the volume is 0.247.
</pre>
</pre>

=={{header|Elixir}}==
=={{header|Elixir}}==
Brute Force:
Brute Force:
Line 1,225: Line 1,274:
maximum = Item.new(0.25, 25, 0)
maximum = Item.new(0.25, 25, 0)
Knapsack.solve_unbounded(items, maximum)</lang>
Knapsack.solve_unbounded(items, maximum)</lang>

{{out}}
{{out}}
<pre>
<pre>Maximum value achievable is 54500 volume weight value
Maximum value achievable is 54500 volume weight value
[gold: 11, ichor: 0, panacea: 9] => 0.247, 24.7, 54500
[gold: 11, ichor: 0, panacea: 9] => 0.247, 24.7, 54500
[gold: 11, ichor: 5, panacea: 6] => 0.247, 24.8, 54500
[gold: 11, ichor: 5, panacea: 6] => 0.247, 24.8, 54500
Line 1,232: Line 1,283:
[gold: 11, ichor: 15, panacea: 0] => 0.247, 25.0, 54500
[gold: 11, ichor: 15, panacea: 0] => 0.247, 25.0, 54500
</pre>
</pre>

=={{header|Factor}}==
=={{header|Factor}}==
{{output?|Factor|reason}}
This is a brute force solution. It is general enough to be able to provide solutions for any number of different items.
This is a brute force solution. It is general enough to be able to provide solutions for any number of different items.
<lang factor>USING: accessors combinators kernel locals math math.order
<lang factor>USING: accessors combinators kernel locals math math.order
Line 1,276: Line 1,327:
find-max-amounts [ 1 + iota ] map <product-sequence>
find-max-amounts [ 1 + iota ] map <product-sequence>
[ <bounty> ] [ max ] map-reduce ;</lang>
[ <bounty> ] [ max ] map-reduce ;</lang>

=={{header|Forth}}==
=={{header|Forth}}==
<lang forth>\ : value ; immediate
<lang forth>\ : value ; immediate
Line 1,377: Line 1,429:
The traveller's knapsack contains 0 vials of panacea, 15 ampules of ichor,
The traveller's knapsack contains 0 vials of panacea, 15 ampules of ichor,
11 bars of gold, a total value of 54500. ok
11 bars of gold, a total value of 54500. ok

=={{header|Fortran}}==
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
{{works with|Fortran|90 and later}}
Line 1,432: Line 1,485:
This is achieved by carrying 0 panacea, 15 ichor and 11 gold items
This is achieved by carrying 0 panacea, 15 ichor and 11 gold items
The weight to carry is 25.0 and the volume used is 0.247
The weight to carry is 25.0 and the volume used is 0.247

=={{header|Go}}==
=={{header|Go}}==
Recursive brute-force.
Recursive brute-force.
Line 1,500: Line 1,554:
sumCount, sumWeight, sumVolume, sumValue)
sumCount, sumWeight, sumVolume, sumValue)
}</lang>
}</lang>

Output:<pre>Panacea x 9 -> Weight: 2.7 Volume: 0.225 Value: 27000
Output:
<pre>
Panacea x 9 -> Weight: 2.7 Volume: 0.225 Value: 27000
Ichor x 0 -> Weight: 0.0 Volume: 0.000 Value: 0
Ichor x 0 -> Weight: 0.0 Volume: 0.000 Value: 0
Gold x 11 -> Weight: 22.0 Volume: 0.022 Value: 27500
Gold x 11 -> Weight: 22.0 Volume: 0.022 Value: 27500
TOTAL ( 20 items) Weight: 24.7 Volume: 0.247 Value: 54500
TOTAL ( 20 items) Weight: 24.7 Volume: 0.247 Value: 54500
</pre>
</pre>

=={{header|Groovy}}==
=={{header|Groovy}}==
Solution: dynamic programming
Solution: dynamic programming
Line 1,554: Line 1,612:
}
}
}</lang>
}</lang>

Output:<pre> Item Order: [panacea, ichor, gold]
Output:
<pre> Item Order: [panacea, ichor, gold]
Elapsed Time: 26.883 s
Elapsed Time: 26.883 s


Line 1,583: Line 1,643:
item: gold (bars) count:11 weight:22.0 Volume:0.022
item: gold (bars) count:11 weight:22.0 Volume:0.022
item: panacea (vials of) count: 9 weight: 2.7 Volume:0.225</pre>
item: panacea (vials of) count: 9 weight: 2.7 Volume:0.225</pre>

While this solver can only be used to detect two of the four possible solutions, the other two may be discovered by noting that 5 ampules of ichor and 3 vials of panacea have the same value and the same volume and only differ by 0.1 in weight. Thus the other two solutions can be derived by substitution as follows:<pre>Total Weight: 24.9
While this solver can only be used to detect two of the four possible solutions, the other two may be discovered by noting that 5 ampules of ichor and 3 vials of panacea have the same value and the same volume and only differ by 0.1 in weight. Thus the other two solutions can be derived by substitution as follows:
<pre>Total Weight: 24.9
Total Volume: 0.247
Total Volume: 0.247
Total Value: 54500
Total Value: 54500
Line 1,596: Line 1,658:
item: ichor (ampules of) count: 5 weight: 1.0 Volume:0.075
item: ichor (ampules of) count: 5 weight: 1.0 Volume:0.075
item: panacea (vials of) count: 6 weight: 1.8 Volume:0.150</pre>
item: panacea (vials of) count: 6 weight: 1.8 Volume:0.150</pre>

=={{header|Haskell}}==
=={{header|Haskell}}==
This is a brute-force solution: it generates a list of every legal combination of items (<tt>options</tt>) and then finds the option of greatest value.
This is a brute-force solution: it generates a list of every legal combination of items (<tt>options</tt>) and then finds the option of greatest value.
Line 1,636: Line 1,699:
main = putStr $ showOpt $ best options
main = putStr $ showOpt $ best options
where best = maximumBy $ comparing $ dotProduct vals</lang>
where best = maximumBy $ comparing $ dotProduct vals</lang>

Output:<pre>panacea: 9
Output:

<pre>panacea: 9
ichor: 0
ichor: 0
gold: 11
gold: 11
Line 1,642: Line 1,708:
total volume: 0.247
total volume: 0.247
total value: 54500</pre>
total value: 54500</pre>

=={{header|HicEst}}==
=={{header|HicEst}}==
<lang hicest>CHARACTER list*1000
<lang hicest>CHARACTER list*1000
Line 1,675: Line 1,742:
value=54500; Panaceas=6; Ichors=5; Golds=11; weight=24.8; volume=0.247;
value=54500; Panaceas=6; Ichors=5; Golds=11; weight=24.8; volume=0.247;
value=54500; Panaceas=9; Ichors=0; Golds=11; weight=24.7; volume=0.247; </lang>
value=54500; Panaceas=9; Ichors=0; Golds=11; weight=24.7; volume=0.247; </lang>

=={{header|J}}==
=={{header|J}}==
Brute force solution.
Brute force solution.
Line 1,695: Line 1,763:
LF
LF
)</lang>
)</lang>
Example output:<pre> KS''
Example output:
<pre> KS''
panacea: 3
panacea: 3
ichor: 10
ichor: 10
Line 1,702: Line 1,771:
total volume: 0.247
total volume: 0.247
total value: 54500</pre>
total value: 54500</pre>

=={{header|Java}}==
=={{header|Java}}==
With recursion for more than 3 items.
With recursion for more than 3 items.
Line 1,840: Line 1,910:


} // class</lang>
} // class</lang>

output:<pre>Maximum value achievable is: 54500
output:
<pre>Maximum value achievable is: 54500
This is achieved by carrying (one solution): 0 panacea, 15 ichor, 11 gold,
This is achieved by carrying (one solution): 0 panacea, 15 ichor, 11 gold,
The weight to carry is: 25 and the volume used is: 0,247</pre>
The weight to carry is: 25 and the volume used is: 0,247</pre>

=={{header|JavaScript}}==
=={{header|JavaScript}}==
Brute force.
Brute force.
Line 1,888: Line 1,961:
item = solutions[i];
item = solutions[i];
document.write("(gold: " + item[0] + ", panacea: " + item[1] + ", ichor: " + item[2] + ")<br>");
document.write("(gold: " + item[0] + ", panacea: " + item[1] + ", ichor: " + item[2] + ")<br>");
}
}</lang>

output:<pre>maximum value: 54500
output:
<pre>maximum value: 54500
(gold: 11, panacea: 0, ichor: 15)
(gold: 11, panacea: 0, ichor: 15)
(gold: 11, panacea: 3, ichor: 10)
(gold: 11, panacea: 3, ichor: 10)
(gold: 11, panacea: 6, ichor: 5)
(gold: 11, panacea: 6, ichor: 5)
(gold: 11, panacea: 9, ichor: 0)</pre>
(gold: 11, panacea: 9, ichor: 0)</pre></lang>

=={{header|Julia}}==
=={{header|Julia}}==
{{libheader|JuMP}}<lang julia>
{{libheader|JuMP}}<lang julia>
Line 1,920: Line 1,996:
println("bars of gold = ", getvalue(bars_of_gold))</lang>
println("bars of gold = ", getvalue(bars_of_gold))</lang>
{{output}}
{{output}}
<pre>
<pre>The optimization problem to be solved is:
The optimization problem to be solved is:
Max 3000 vials_of_panacea + 1800 ampules_of_ichor + 2500 bars_of_gold
Max 3000 vials_of_panacea + 1800 ampules_of_ichor + 2500 bars_of_gold
Subject to
Subject to
Line 1,932: Line 2,009:
vials of panacea = 9.0
vials of panacea = 9.0
ampules of ichor = 0.0
ampules of ichor = 0.0
bars of gold = 11.0</pre>
bars of gold = 11.0
</pre>

=={{header|Kotlin}}==
=={{header|Kotlin}}==
{{trans|C}}
{{trans|C}}
Recursive brute force approach:
Recursive brute force approach:
<lang kotlin>// version 1.1.2
<lang scala>// version 1.1.2


data class Item(val name: String, val value: Double, val weight: Double, val volume: Double)
data class Item(val name: String, val value: Double, val weight: Double, val volume: Double)
Line 2,005: Line 2,084:


{{out}}
{{out}}
<pre>
<pre>Item Chosen Number Value Weight Volume
Item Chosen Number Value Weight Volume
----------- ------ ----- ------ ------
----------- ------ ----- ------ ------
panacea 9 27000 2.7 0.23
panacea 9 27000 2.7 0.23
gold 11 27500 22.0 0.02
gold 11 27500 22.0 0.02
----------- ------ ----- ------ ------
----------- ------ ----- ------ ------
2 items 20 54500 24.7 0.25</pre>
2 items 20 54500 24.7 0.25
</pre>

=={{header|M4}}==
=={{header|M4}}==
A brute force solution:
A brute force solution:
Line 2,047: Line 2,129:
divert
divert
mv best</lang>
mv best</lang>
Output:
Output:<pre>54500 (0,15,11) (3,10,11) (6,5,11) (9,0,11)</pre>
<pre>54500 (0,15,11) (3,10,11) (6,5,11) (9,0,11)</pre>

=={{header|Lua}}==
=={{header|Lua}}==
{{output?|Lua|reason}}
<lang lua>items = { ["panaea"] = { ["value"] = 3000, ["weight"] = 0.3, ["volume"] = 0.025 },
<lang lua>items = { ["panaea"] = { ["value"] = 3000, ["weight"] = 0.3, ["volume"] = 0.025 },
["ichor"] = { ["value"] = 1800, ["weight"] = 0.2, ["volume"] = 0.015 },
["ichor"] = { ["value"] = 1800, ["weight"] = 0.2, ["volume"] = 0.015 },
Line 2,086: Line 2,169:
print( k, v )
print( k, v )
end</lang>
end</lang>

=={{header|Mathematica}}==
=={{header|Mathematica}}==
Brute force algorithm:
Brute force algorithm:
Line 2,106: Line 2,190:
p:0 i:15 v:11</lang>
p:0 i:15 v:11</lang>
The volume for all of those is the same, the 'best' solution would be the one that has the least weight: that would the first solution.
The volume for all of those is the same, the 'best' solution would be the one that has the least weight: that would the first solution.

=={{header|Mathprog}}==
=={{header|Mathprog}}==
<lang mathprog>/*Knapsack
<lang mathprog>/*Knapsack
Line 2,137: Line 2,222:
end;</lang>
end;</lang>
The solution produced is at [[Knapsack problem/Unbounded/Mathprog]].
The solution produced is at [[Knapsack problem/Unbounded/Mathprog]].

=={{header|Modula-3}}==
=={{header|Modula-3}}==
{{trans|Fortran}}
{{trans|Fortran}}
Line 2,187: Line 2,273:
Put("The weight of this carry is " & Real(totalWeight) & " and the volume used is " & Real(totalVolume) & "\n");
Put("The weight of this carry is " & Real(totalWeight) & " and the volume used is " & Real(totalVolume) & "\n");
END Knapsack.</lang>
END Knapsack.</lang>
Output:
Output:<pre>Maximum value achievable is 54500
<pre>Maximum value achievable is 54500
This is achieved by carrying 0 panacea, 15 ichor and 11 gold items
This is achieved by carrying 0 panacea, 15 ichor and 11 gold items
The weight of this carry is 25 and the volume used is 0.247</pre>
The weight of this carry is 25 and the volume used is 0.247</pre>

=={{header|OCaml}}==
=={{header|OCaml}}==
This is a brute-force solution: it generates a list of every legal combination of items and then finds the best results:
This is a brute-force solution: it generates a list of every legal combination of items and then finds the best results:
Line 2,268: Line 2,356:


let () = List.iter print best_results</lang>
let () = List.iter print best_results</lang>

outputs:<pre>Maximum value: 54500
outputs:
<pre>Maximum value: 54500
Total weight: 24.7
Total weight: 24.7
Total volume: 0.247
Total volume: 0.247
Line 2,287: Line 2,377:
Total volume: 0.247
Total volume: 0.247
Containing: 0 panacea, 15 ichor, 11 gold</pre>
Containing: 0 panacea, 15 ichor, 11 gold</pre>

=={{header|OOCalc}}==
=={{header|OOCalc}}==
OpenOffice.org Calc has (several) linear solvers. To solve this task, first copy in the table from the task description, then add the extra columns:
OpenOffice.org Calc has (several) linear solvers. To solve this task, first copy in the table from the task description, then add the extra columns:
Line 2,306: Line 2,397:
to produce in seconds:
to produce in seconds:
:[[File:Unbounded Knapsack problem result.PNG|center|Table solved]]
:[[File:Unbounded Knapsack problem result.PNG|center|Table solved]]

=={{header|Oz}}==
=={{header|Oz}}==
Using constraint propagation and branch and bound search:
Using constraint propagation and branch and bound search:
Line 2,334: Line 2,426:


If you study the output, you see how the weight and volume equations automagically constrain the domain of the three variables.
If you study the output, you see how the weight and volume equations automagically constrain the domain of the three variables.
Afterwards SearchBest only has to evaluate 38 different combinations to find an optimal solution:<pre>Search:
Afterwards SearchBest only has to evaluate 38 different combinations to find an optimal solution:

<pre>Search:
0#solution(gold:_{0#134217726} ichor:_{0#134217726} panacea:_{0#134217726})
0#solution(gold:_{0#134217726} ichor:_{0#134217726} panacea:_{0#134217726})
1#solution(gold:_{0#12} ichor:_{0#125} panacea:_{0#83})
1#solution(gold:_{0#12} ichor:_{0#125} panacea:_{0#83})
Line 2,379: Line 2,473:
Result:
Result:
solution(gold:11 ichor:15 panacea:0)
solution(gold:11 ichor:15 panacea:0)
total value: 54500</pre>
total value: 54500
</pre>

=={{header|Pascal}}==
=={{header|Pascal}}==
With ideas from C, Fortran and Modula-3.
With ideas from C, Fortran and Modula-3.
Line 2,436: Line 2,532:
writeln ('The weight of this carry is ', totalWeight:6:3, ' and the volume used is ', totalVolume:6:4);
writeln ('The weight of this carry is ', totalWeight:6:3, ' and the volume used is ', totalVolume:6:4);
end.</lang>
end.</lang>
Output:<pre>:> ./Knapsack
Output:
<pre>:> ./Knapsack
Maximum value achievable is 54500
Maximum value achievable is 54500
This is achieved by carrying 0 panacea, 15 ichor and 11 gold items
This is achieved by carrying 0 panacea, 15 ichor and 11 gold items
The weight of this carry is 25.000 and the volume used is 0.2470</pre>
The weight of this carry is 25.000 and the volume used is 0.2470
</pre>

=={{header|Perl}}==
=={{header|Perl}}==
Dynamic programming solution. Before you ask, no, it's actually slower for the given data set. See the alternate data set.
Dynamic programming solution. Before you ask, no, it's actually slower for the given data set. See the alternate data set.
Line 2,513: Line 2,612:


print "\nCache hit: $hits\tmiss: $misses\n";</lang>
print "\nCache hit: $hits\tmiss: $misses\n";</lang>

Output:<pre>Max value 54500, with:
Output:<pre>Max value 54500, with:
Item Qty Weight Vol Value
Item Qty Weight Vol Value
Line 2,523: Line 2,623:
Cache hit: 0 miss: 218</pre>
Cache hit: 0 miss: 218</pre>
Cache info is not pertinent to this task, just some info.
Cache info is not pertinent to this task, just some info.

=={{header|Perl 6}}==
=={{header|Perl 6}}==
{{Works with|rakudo|2016.08}}
{{Works with|rakudo|2016.08}}
Line 2,569: Line 2,670:
say "panacea\tichor\tgold";
say "panacea\tichor\tgold";
.join("\t").say for @solutions;</lang>
.join("\t").say for @solutions;</lang>
'''Output:'''<pre>maximum value is 54500
'''Output:'''
<pre>maximum value is 54500
possible solutions:
possible solutions:
panacea ichor gold
panacea ichor gold
Line 2,576: Line 2,678:
6 5 11
6 5 11
9 0 11</pre>
9 0 11</pre>

=={{header|Phix}}==
=={{header|Phix}}==
For each goodie, fill yer boots, then (except for the last) recursively try with fewer and fewer.<br>
For each goodie, fill yer boots, then (except for the last) recursively try with fewer and fewer.<br>
Line 2,627: Line 2,730:
printf(1," [weight:%g, volume:%g, %d attempts]\n",
printf(1," [weight:%g, volume:%g, %d attempts]\n",
{weight,volume,attempts})</lang>
{weight,volume,attempts})</lang>
{{out}}
{{out}}<pre>Profit 54500: 9 panacea, 0 ichor, 11 shiney shiney
<pre>
[weight:24.7, volume:0.247, 98 attempts]</pre>
Profit 54500: 9 panacea, 0 ichor, 11 shiney shiney
[weight:24.7, volume:0.247, 98 attempts]
</pre>
You get the same result whatever order the goodies are in, but with a different number of attempts, gold/ichor/panacea being the
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.
highest at 204.

=={{header|PicoLisp}}==
=={{header|PicoLisp}}==
Brute force solution
Brute force solution
Line 2,657: Line 2,764:
(apply tab X (4 2 8 5 5 7) N "x") ) )
(apply tab X (4 2 8 5 5 7) N "x") ) )
(tab (14 5 5 7) NIL (sum cadr K) (sum caddr K) (sum cadddr K)) )</lang>
(tab (14 5 5 7) NIL (sum cadr K) (sum caddr K) (sum cadddr K)) )</lang>
Output:
Output:<pre> 15 x ichor 2 15 1800
<pre> 15 x ichor 2 15 1800
11 x gold 20 2 2500
11 x gold 20 2 2500
250 247 54500</pre>
250 247 54500</pre>

=={{header|PowerShell}}==
=={{header|PowerShell}}==
{{works with|PowerShell|3.0}}
{{works with|PowerShell|3.0}}
Line 2,729: Line 2,838:
6 vials of panacea, 5 ampules of ichor, and 11 bars of gold worth a total of 54500.
6 vials of panacea, 5 ampules of ichor, and 11 bars of gold worth a total of 54500.
9 vials of panacea, 0 ampules of ichor, and 11 bars of gold worth a total of 54500.</pre>
9 vials of panacea, 0 ampules of ichor, and 11 bars of gold worth a total of 54500.</pre>

=={{header|Prolog}}==
=={{header|Prolog}}==
Works with SWI-Prolog and <b>library simplex</b> written by <b>Markus Triska</b>.
Works with SWI-Prolog and <b>library simplex</b> written by <b>Markus Triska</b>.
Line 2,817: Line 2,927:
Vo2 is Vo1 + Votemp ),
Vo2 is Vo1 + Votemp ),
print_results(S, A0, A1, A2, A3, A4, T, TN, Va2, W2, Vo2).</lang>
print_results(S, A0, A1, A2, A3, A4, T, TN, Va2, W2, Vo2).</lang>
Output :<pre> ?- knapsack.
Output :
<pre> ?- knapsack.
% 145,319 inferences, 0.078 CPU in 0.079 seconds (99% CPU, 1860083 Lips)
% 145,319 inferences, 0.078 CPU in 0.079 seconds (99% CPU, 1860083 Lips)
Nb Items Value Weigth Volume
Nb Items Value Weigth Volume
Line 2,824: Line 2,935:
54500 25.00 0.247
54500 25.00 0.247
true </pre>
true </pre>

=={{header|PureBasic}}==
=={{header|PureBasic}}==
{{trans|Fortran}}
{{trans|Fortran}}
Line 2,916: Line 3,028:
Press Enter to quit</tt>
Press Enter to quit</tt>

=={{header|Python}}==
=={{header|Python}}==
See [[Knapsack Problem/Python]]
See [[Knapsack Problem/Python]]

=={{header|R}}==
=={{header|R}}==
Brute force method
Brute force method
Line 2,947: Line 3,061:
2171 3 10 11
2171 3 10 11
2223 0 15 11
2223 0 15 11



Using Dynamic Programming
Using Dynamic Programming

<lang r>Data_<-structure(list(item = c("Panacea", "Ichor", "Gold"), value = c(3000,
<lang r>
Data_<-structure(list(item = c("Panacea", "Ichor", "Gold"), value = c(3000,
1800, 2500), weight = c(3, 2, 20), volume = c(25, 15, 2)), .Names = c("item",
1800, 2500), weight = c(3, 2, 20), volume = c(25, 15, 2)), .Names = c("item",
"value", "weight", "volume"), row.names = c(NA, 3L), class = "data.frame")
"value", "weight", "volume"), row.names = c(NA, 3L), class = "data.frame")
Line 3,036: Line 3,153:
}
}


main_knapsack(Data_, 250, 250)</lang>
main_knapsack(Data_, 250, 250)
</lang>
<lang r>
<lang r>
Output:
Output:
Line 3,043: Line 3,161:
You must carry: Panacea (x 9 )
You must carry: Panacea (x 9 )
</lang>
</lang>

=={{header|Racket}}==
=={{header|Racket}}==

<lang racket>#lang racket
<lang racket>
#lang racket


(struct item (name explanation value weight volume) #:prefab)
(struct item (name explanation value weight volume) #:prefab)
Line 3,082: Line 3,203:


(call-with-values (λ() (fill-sack items 0.25 25 '() 0))
(call-with-values (λ() (fill-sack items 0.25 25 '() 0))
(λ(sacks total) (for ([s sacks]) (display-sack s total))))</lang>
(λ(sacks total) (for ([s sacks]) (display-sack s total))))
</lang>

{{out}}
{{out}}
<pre>Take 11 gold (bars)
<pre>Take 11 gold (bars)
Line 3,103: Line 3,226:
Take 9 panacea (vials of)
Take 9 panacea (vials of)
GRAND TOTAL: 54500</pre>
GRAND TOTAL: 54500</pre>

=={{header|REXX}}==
=={{header|REXX}}==
{{trans|Fortran}}
{{trans|Fortran}}
Line 3,142: Line 3,266:
say left('', 40) "total volume: " maxV / 1
say left('', 40) "total volume: " maxV / 1
/*stick a fork in it, we're all done. */</lang>
/*stick a fork in it, we're all done. */</lang>
'''output'''<pre> panacea in sack: 0
'''output'''
<pre>
panacea in sack: 0
ichors in sack: 15
ichors in sack: 15
gold items in sack: 11
gold items in sack: 11
Line 3,149: Line 3,275:
total value: 54500
total value: 54500
total weight: 25
total weight: 25
total volume: 0.247</pre>
total volume: 0.247
</pre>

===displays all solutions===
===displays all solutions===
<lang rexx>/*REXX program solves the knapsack/unbounded problem: highest value, weight, and volume.*/
<lang rexx>/*REXX program solves the knapsack/unbounded problem: highest value, weight, and volume.*/
Line 3,191: Line 3,319:
end /*j*/
end /*j*/
/*stick a fork in it, we're all done. */</lang>
/*stick a fork in it, we're all done. */</lang>
'''output'''
'''output'''<pre>▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ solution 1
<pre>
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ solution 1
panacea in sack: 0
panacea in sack: 0
ichors in sack: 15
ichors in sack: 15
Line 3,229: Line 3,359:
total value: 54500
total value: 54500
total weight: 24.7
total weight: 24.7
total volume: 0.247</pre>
total volume: 0.247
</pre>

=={{header|Ruby}}==
=={{header|Ruby}}==
Brute force method, {{trans|Tcl}}
Brute force method, {{trans|Tcl}}
Line 3,270: Line 3,402:
end</lang>
end</lang>
{{out}}
{{out}}
<pre>
<pre>The maximal solution has value 54500
The maximal solution has value 54500
ichor= 0, panacea= 9, gold=11 -- weight:24.7, volume=0.247
ichor= 0, panacea= 9, gold=11 -- weight:24.7, volume=0.247
ichor= 5, panacea= 6, gold=11 -- weight:24.8, volume=0.247
ichor= 5, panacea= 6, gold=11 -- weight:24.8, volume=0.247
ichor=10, panacea= 3, gold=11 -- weight:24.9, volume=0.247
ichor=10, panacea= 3, gold=11 -- weight:24.9, volume=0.247
ichor=15, panacea= 0, gold=11 -- weight:25.0, volume=0.247</pre>
ichor=15, panacea= 0, gold=11 -- weight:25.0, volume=0.247</pre>

=={{header|SAS}}==
=={{header|SAS}}==
This is yet another brute force solution.
This is yet another brute force solution.
Line 3,307: Line 3,441:
var panacea ichor gold vals;
var panacea ichor gold vals;
run;</lang>
run;</lang>
Output:
Output:<pre> Obs panacea ichor gold vals
<pre>
Obs panacea ichor gold vals


1 0 15 11 54500
1 0 15 11 54500
2 3 10 11 54500
2 3 10 11 54500
3 6 5 11 54500
3 6 5 11 54500
4 9 0 11 54500</pre>
4 9 0 11 54500
</pre>

Use SAS/OR:
Use SAS/OR:
<lang sas>/* create SAS data set */
<lang sas>/* create SAS data set */
Line 3,354: Line 3,492:
for {s in 1.._NSOL_} print {i in ITEMS} NumSelected[i].sol[s];
for {s in 1.._NSOL_} print {i in ITEMS} NumSelected[i].sol[s];
quit;</lang>
quit;</lang>

MILP solver output:<pre>TotalValue
MILP solver output:
<pre>
TotalValue
54500
54500


Line 3,360: Line 3,501:
gold (bars) 11
gold (bars) 11
ichor (ampules of) 0
ichor (ampules of) 0
panacea (vials of) 9 </pre>
panacea (vials of) 9
</pre>
CLP solver output:<pre>TotalValue

CLP solver output:
<pre>
TotalValue
54500
54500


Line 3,382: Line 3,527:
gold (bars) 11
gold (bars) 11
ichor (ampules of) 0
ichor (ampules of) 0
panacea (vials of) 9 </pre>
panacea (vials of) 9
</pre>

=={{header|Scala}}==
=={{header|Scala}}==
===Functional approach (Tail recursive)===
<lang Scala>import scala.annotation.tailrec


'''Functional approach''' (Tail recursive)

<lang scala>import scala.annotation.tailrec
object UnboundedKnapsack extends App {
object UnboundedKnapsack extends App {
private val (maxWeight, maxVolume) = (BigDecimal(25.0), BigDecimal(0.25))
private val (maxWeight, maxVolume) = (BigDecimal(25.0), BigDecimal(0.25))
private val items = Seq(Item("panacea", 3000, 0.3, 0.025), Item("ichor", 1800, 0.2, 0.015), Item("gold", 2500, 2.0, 0.002))
private val items = Seq(Item("panacea", 3000, 0.3, 0.025), Item("ichor", 1800, 0.2, 0.015), Item("gold", 2500, 2.0, 0.002))

@tailrec
@tailrec
private def packer(notPacked: Seq[Knapsack], packed: Seq[Knapsack]): Seq[Knapsack] = {
private def packer(notPacked: Seq[Knapsack], packed: Seq[Knapsack]): Seq[Knapsack] = {
def fill(knapsack: Knapsack): Seq[Knapsack] = items.map(i => Knapsack(i +: knapsack.bagged))
def fill(knapsack: Knapsack): Seq[Knapsack] = items.map(i => Knapsack(i +: knapsack.bagged))

def stuffer(Seq: Seq[Knapsack]): Seq[Knapsack] = // Cause brute force
def stuffer(Seq: Seq[Knapsack]): Seq[Knapsack] = // Cause brute force
Seq.map(k => Knapsack(k.bagged.sortBy(_.name))).distinct
Seq.map(k => Knapsack(k.bagged.sortBy(_.name))).distinct

if (notPacked.isEmpty) packed.sortBy(-_.totValue).take(4)
if (notPacked.isEmpty) packed.sortBy(-_.totValue).take(4)
else packer(stuffer(notPacked.flatMap(fill)).filter(_.isNotFull), notPacked ++ packed)
else packer(stuffer(notPacked.flatMap(fill)).filter(_.isNotFull), notPacked ++ packed)
}
}

private case class Item(name: String, value: Int, weight: BigDecimal, volume: BigDecimal)
private case class Item(name: String, value: Int, weight: BigDecimal, volume: BigDecimal)

private case class Knapsack(bagged: Seq[Item]) {
private case class Knapsack(bagged: Seq[Item]) {
def isNotFull: Boolean = totWeight <= maxWeight && totVolume <= maxVolume
def isNotFull: Boolean = totWeight <= maxWeight && totVolume <= maxVolume

override def toString = s"[${show(bagged)} | value: $totValue, weight: $totWeight, volume: $totVolume]"
override def toString = s"[${show(bagged)} | value: $totValue, weight: $totWeight, volume: $totVolume]"

def totValue: Int = bagged.map(_.value).sum
def totValue: Int = bagged.map(_.value).sum

private def totVolume = bagged.map(_.volume).sum
private def totVolume = bagged.map(_.volume).sum

private def totWeight = bagged.map(_.weight).sum
private def totWeight = bagged.map(_.weight).sum

private def show(is: Seq[Item]) =
private def show(is: Seq[Item]) =
(items.map(_.name) zip items.map(i => is.count(_ == i)))
(items.map(_.name) zip items.map(i => is.count(_ == i)))
Line 3,420: Line 3,569:
.mkString(", ")
.mkString(", ")
}
}

packer(items.map(i => Knapsack(Seq(i))), Nil).foreach(println)
packer(items.map(i => Knapsack(Seq(i))), Nil).foreach(println)
}</lang>
}</lang>

{{Out}}
{{out}}
<pre>[panacea: 0, ichor: 15, gold: 11 | value: 54500, weight: 25.0, volume: 0.247]

<pre>
[panacea: 0, ichor: 15, gold: 11 | value: 54500, weight: 25.0, volume: 0.247]
[panacea: 3, ichor: 10, gold: 11 | value: 54500, weight: 24.9, volume: 0.247]
[panacea: 3, ichor: 10, gold: 11 | value: 54500, weight: 24.9, volume: 0.247]
[panacea: 6, ichor: 5, gold: 11 | value: 54500, weight: 24.8, volume: 0.247]
[panacea: 6, ichor: 5, gold: 11 | value: 54500, weight: 24.8, volume: 0.247]
[panacea: 9, ichor: 0, gold: 11 | value: 54500, weight: 24.7, volume: 0.247]</pre>
[panacea: 9, ichor: 0, gold: 11 | value: 54500, weight: 24.7, volume: 0.247]
</pre>
{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/1fRBQs5/2 ScalaFiddle (JavaScript)] or by [https://scastie.scala-lang.org/S4oGElcwQkCMesfuSRKfkw Scastie (JVM).].

=={{header|Seed7}}==
=={{header|Seed7}}==
<lang seed7>$ include "seed7_05.s7i";
<lang seed7>$ include "seed7_05.s7i";
Line 3,481: Line 3,634:
writeln("The weight of this carry is " <& best.weight <& " and the volume used is " <& best.volume digits 4);
writeln("The weight of this carry is " <& best.weight <& " and the volume used is " <& best.volume digits 4);
end func;</lang>
end func;</lang>

Output:<pre>Maximum value achievable is 54500
Output:
<pre>
Maximum value achievable is 54500
This is achieved by carrying 0 panacea, 15 ichor and 11 gold items
This is achieved by carrying 0 panacea, 15 ichor and 11 gold items
The weight of this carry is 25.0 and the volume used is 0.2470</pre>
The weight of this carry is 25.0 and the volume used is 0.2470
</pre>

=={{header|Sidef}}==
=={{header|Sidef}}==
{{trans|Perl}}
{{trans|Perl}}
Line 3,552: Line 3,710:
EOT</lang>
EOT</lang>
{{out}}
{{out}}
<pre>
<pre>Max value 54500, with:
Max value 54500, with:
Item Qty Weight Vol Value
Item Qty Weight Vol Value
--------------------------------------------------
--------------------------------------------------
Line 3,558: Line 3,717:
gold: 11 22 0.022 27500
gold: 11 22 0.022 27500
--------------------------------------------------
--------------------------------------------------
Total: 24 0.247 54500</pre>
Total: 24 0.247 54500
</pre>

=={{header|Tcl}}==
=={{header|Tcl}}==
The following code uses brute force, but that's tolerable as long as it takes just a split second to find all 4 solutions. The use of arrays makes the quote quite legible:
The following code uses brute force, but that's tolerable as long as it takes just a split second to find all 4 solutions. The use of arrays makes the quote quite legible:
Line 3,592: Line 3,753:
}
}
main $argv</lang>
main $argv</lang>

<pre>$ time tclsh85 /Tcl/knapsack.tcl
<pre>$ time tclsh85 /Tcl/knapsack.tcl
maxval: 54500, best: {i 0 p 9 g 11} {i 5 p 6 g 11} {i 10 p 3 g 11} {i 15 p 0 g 11}
maxval: 54500, best: {i 0 p 9 g 11} {i 5 p 6 g 11} {i 10 p 3 g 11} {i 15 p 0 g 11}
Line 3,598: Line 3,760:
user 0m0.015s
user 0m0.015s
sys 0m0.015s</pre>
sys 0m0.015s</pre>

=={{header|Ursala}}==
=={{header|Ursala}}==
The algorithm is to enumerate all packings with up to the maximum of each item,
The algorithm is to enumerate all packings with up to the maximum of each item,
Line 3,616: Line 3,779:


human_readable = ~&p/*<'panacea','ichor','gold'> solutions</lang>
human_readable = ~&p/*<'panacea','ichor','gold'> solutions</lang>
output:<pre><
output:
<pre><
<'panacea': 0,'ichor': 15,'gold': 11>,
<'panacea': 0,'ichor': 15,'gold': 11>,
<'panacea': 3,'ichor': 10,'gold': 11>,
<'panacea': 3,'ichor': 10,'gold': 11>,
<'panacea': 6,'ichor': 5,'gold': 11>,
<'panacea': 6,'ichor': 5,'gold': 11>,
<'panacea': 9,'ichor': 0,'gold': 11>></pre>
<'panacea': 9,'ichor': 0,'gold': 11>></pre>

=={{header|Visual Basic}}==
=={{header|Visual Basic}}==
See: [[Knapsack Problem/Visual Basic]]
See: [[Knapsack Problem/Visual Basic]]
Line 3,656: Line 3,821:
54500 24.8 0.247 6 5 11
54500 24.8 0.247 6 5 11
54500 24.9 0.247 3 10 11
54500 24.9 0.247 3 10 11
54500 25 0.247 0 15 11 </pre>
54500 25 0.247 0 15 11
</pre>

=={{header|zkl}}==
=={{header|zkl}}==
{{trans|D}}
{{trans|D}}
Line 3,682: Line 3,849:
cprod3 is the Cartesian product of three lists or iterators.
cprod3 is the Cartesian product of three lists or iterators.
{{out}}
{{out}}
<pre>
<pre>Maximum value achievable is 54,500
Maximum value achievable is 54,500
This is achieved by carrying (one solution): 9 panacea, 0 ichor and 11 gold
This is achieved by carrying (one solution): 9 panacea, 0 ichor and 11 gold
The weight to carry is 24.7 and the volume used is 0.247</pre>
The weight to carry is 24.7 and the volume used is 0.247
</pre>

[[Category:Puzzles]]
[[Category:Puzzles]]
Retrieved from "https://rosettacode.org/wiki/Knapsack_problem/Unbounded"