Knapsack problem/Unbounded: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
(7 intermediate revisions by 5 users not shown) | |||
Line 81:
{{trans|Python}}
<
Int value
Float weight, volume
Line 113:
print(‘Maximum value achievable is ’best.value)
print(‘This is achieved by carrying (one solution) #. panacea, #. ichor and #. gold’.format(best_amounts[0], best_amounts[1], best_amounts[2]))
print(‘The weight to carry is #2.1 and the volume used is #.3’.format(best.weight, best.volume))</
{{out}}
Line 125:
{{trans|Visual Basic}}
The program uses two ASSIST macros (XDECO,XPRNT) to keep the code as short as possible.
<
KNAPSACK CSECT
USING KNAPSACK,R13 base register
Line 321:
PG DS CL72
YREGS
END KNAPSACK</
{{out}}
<pre>
Line 333:
=={{header|Ada}}==
{{trans|Python}}
<
procedure Knapsack_Unbounded is
Line 397:
Ada.Text_IO.Put_Line ("Ichor: " & Natural'Image (Best_Amounts (2)));
Ada.Text_IO.Put_Line ("Gold: " & Natural'Image (Best_Amounts (3)));
end Knapsack_Unbounded;</
=={{header|ALGOL 68}}==
{{trans|Python}}<
[]BOUNTY items = (
Line 509:
name OF items, max items));
printf(($" The weight to carry is "f(d)", and the volume used is "f(d)l$,
weight OF max, volume OF max))</
<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
Line 516:
=={{header|AutoHotkey}}==
Brute Force.
<
Value = 3000,1800,2500
Weight= 3,2,20 ; *10
Line 540:
}
}
MsgBox Value = %$%`n`nPanacea`tIchor`tGold`tWeight`tVolume`n%t%</
=={{header|Bracmat}}==
<
( things
= (panacea.3000.3/10.25/1000)
Line 613:
!knapsack;
</syntaxhighlight>
Output:
<pre>Take 15 items of ichor.
Line 623:
figures out the best (highest value) set by brute forcing every possible subset.
<
#include <stdlib.h>
Line 681:
return 0;
}
</syntaxhighlight>
{{output}}<pre>9 panacea
Line 690:
=={{header|C sharp|C#}}==
<
a 30 3 25
b 18 2 15
Line 735:
return new uint[] { a0, b0, c0 };
}
}</
=={{header|C_sharp|C#}}==
<
This model finds the integer optimal packing of a knapsack
Line 792:
}
}
}</
Produces:
<pre>
Line 830:
take(Ichor): 0
take(Gold): 11
</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
struct Item {
std::string name;
int32_t value;
double weight;
double volume;
};
const std::vector<Item> items = {
Item("panacea", 3000, 0.3, 0.025),
Item("ichor", 1800, 0.2, 0.015),
Item("gold", 2500, 2.0, 0.002)
};
constexpr double MAX_WEIGHT = 25.0;
constexpr double MAX_VOLUME = 0.25;
std::vector<int32_t> count(items.size(), 0);
std::vector<int32_t> best(items.size(), 0);
int32_t best_value = 0;
void knapsack(const uint64_t& i, const int32_t& value, const double& weight, const double& volume) {
if ( i == items.size() ) {
if ( value > best_value ) {
best_value = value;
best = count;
}
return;
}
int32_t measure1 = (int32_t) std::floor( weight / items[i].weight );
int32_t measure2 = (int32_t) std::floor( volume / items[i].volume );
int32_t measure = std::min(measure1, measure2);
count[i] = measure;
while ( count[i] >= 0 ) {
knapsack(
i + 1,
value + count[i] * items[i].value,
weight - count[i] * items[i].weight,
volume - count[i] * items[i].volume
);
count[i]--;
}
}
int main() {
knapsack(0, 0, MAX_WEIGHT, MAX_VOLUME);
std::cout << "Item Chosen Number Value Weight Volume" << std::endl;
std::cout << "----------- ------ ----- ------ ------" << std::endl;
int32_t item_count = 0;
int32_t number_sum = 0;
double weight_sum = 0.0;
double volume_sum = 0.0;
for ( uint64_t i = 0; i < items.size(); ++i ) {
if ( best[i] == 0 ) {
continue;
}
item_count++;
std::string name = items[i].name;
int32_t number = best[i];
int32_t value = items[i].value * number;
double weight = items[i].weight * number;
double volume = items[i].volume * number;
number_sum += number;
weight_sum += weight;
volume_sum += volume;
std::cout << std::setw(11) << name << std::setw(6) << number << std::setw(8) << value << std::fixed
<< std::setw(8) << std::setprecision(2) << weight
<< std::setw(8) << std::setprecision(2) << volume << std::endl;
}
std::cout << "----------- ------ ----- ------ ------" << std::endl;
std::cout << std::setw(5) << item_count << " items" << std::setw(6) << number_sum << std::setw(8) << best_value
<< std::setw(8) << weight_sum << std::setw(8) << volume_sum << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
Item Chosen Number Value Weight Volume
----------- ------ ----- ------ ------
panacea 9 27000 2.70 0.23
gold 11 27500 22.00 0.02
----------- ------ ----- ------ ------
2 items 20 54500 24.70 0.25
</pre>
=={{header|Clojure}}==
<
(defn total [key items quantities]
Line 841 ⟶ 939:
(let [mcw (/ max-weight (:weight item))
mcv (/ max-volume (:volume item))]
(min mcw mcv)))</
We have an <tt>item</tt> struct to contain the data for both contents and the knapsack. The <tt>total</tt> function returns the sum of a particular attribute across all items times their quantities. Finally, the <tt>max-count</tt> function returns the most of that item that could fit given the constraints (used as the upper bound on the combination). Now the real work:
<
(let [pan (struct item 3000 0.3 0.025)
ich (struct item 1800 0.2 0.015)
Line 861 ⟶ 959:
i (iters ich)
g (iters gol)]
[p i g])))))</
The <tt>knapsacks</tt> function returns a lazy sequence of all valid knapsacks, with the particular content quantities as metadata. The work of realizing each knapsack is done in parallel via the <tt>pmap</tt> function. The following then finds the best by value, and prints the result.
<
(reduce #(if (> (:value %1) (:value %2)) %1 %2) ks))
Line 872 ⟶ 970:
(println "Total weight: " (float w))
(println "Total volume: " (float v))
(println "Containing: " p "Panacea," i "Ichor," g "Gold")))</
Calling <tt>(print-knapsack (best-by-value (knapsacks)))</tt> would result in something like:
<pre>Maximum value: 54500
Line 879 ⟶ 977:
Containing: 9 Panacea, 0 Ichor, 11 Gold</pre>
Further, we could find all "best" knapsacks rather simply (albeit at the cost of some efficiency):
<
(let [b (best-by-value ks)]
(filter #(= (:value b) (:value %)) ks)))
Line 886 ⟶ 984:
(doseq [k ks]
(print-knapsack k)
(println)))</
Calling <tt>(print-knapsacks (all-best-by-value (knapsacks)))</tt> would result in something like:
<pre>
Line 912 ⟶ 1,010:
=={{header|Common Lisp}}==
A dynamic programming <i>O(maxVolume × maxWeight × nItems)</i> solution, where volumes and weights are integral values.
<
"Items is a list of lists of the form (name value weight volume) where weight
and value are integers. max-volume and max-weight, also integers, are the
Line 955 ⟶ 1,053:
b-items (list* item o-items)))))))
(setf (aref maxes v w)
(list b-value b-items b-volume b-weight))))))))</
Use, having multiplied volumes and weights as to be integral:
Line 977 ⟶ 1,075:
=={{header|D}}==
{{trans|Python}}
<
import std.stdio, std.algorithm, std.typecons, std.conv;
Line 1,027 ⟶ 1,125:
writefln("The weight to carry is %4.1f and the volume used is %5.3f",
best.weight, best.volume);
}</
{{out}}
<pre>Maximum value achievable is 54500
Line 1,035 ⟶ 1,133:
===Alternative Version===
The output is the same.
<
import std.stdio, std.algorithm, std.typecons, std.range, std.conv;
Line 1,060 ⟶ 1,158:
writefln("This is achieved by carrying (one solution) %d panacea, %d ichor and %d gold", best[1][]);
writefln("The weight to carry is %4.1f and the volume used is %5.3f", best[0][1..$]);
}</
=={{header|E}}==
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.
<
/** A data type representing a bunch of stuff (or empty space). */
Line 1,143 ⟶ 1,241:
:= makeQuantity( 0, 25, 0.250, [].asMap())
printBest(emptyKnapsack, [panacea, ichor, gold])</
=={{header|EchoLisp}}==
Use a cache, and multiply by 10^n to get an integer problem.
<
(require 'struct)
(require 'hash)
Line 1,219 ⟶ 1,317:
→ 218
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
KNAPSACK
Line 1,305 ⟶ 1,403:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,315 ⟶ 1,413:
=={{header|Elixir}}==
Brute Force:
<
defstruct volume: 0.0, weight: 0.0, value: 0
def new(volume, weight, value) do
Line 1,365 ⟶ 1,463:
gold: Item.new(0.002, 2.0, 2500) }
maximum = Item.new(0.25, 25, 0)
Knapsack.solve_unbounded(items, maximum)</
{{out}}
Line 1,378 ⟶ 1,476:
=={{header|Factor}}==
This is a brute force solution. It is general enough to be able to provide solutions for any number of different items.
<
math.vectors sequences sequences.product combinators.short-circuit ;
IN: knapsack
Line 1,418 ⟶ 1,516:
: best-bounty ( -- bounty )
find-max-amounts [ 1 + iota ] map <product-sequence>
[ <bounty> ] [ max ] map-reduce ;</
=={{header|Forth}}==
<
: weight cell+ ;
: volume 2 cells + ;
Line 1,480 ⟶ 1,578:
solve-ichor ;
solve-panacea .solution</
Or like this...
<
0 VALUE ampules
0 VALUE bars
Line 1,515 ⟶ 1,613:
LOOP
LOOP
.SOLUTION ;</
With the result...
Line 1,525 ⟶ 1,623:
{{works with|Fortran|90 and later}}
A straight forward 'brute force' approach
<
IMPLICIT NONE
Line 1,572 ⟶ 1,670:
WRITE(*, "(A,F4.1,A,F5.3)") "The weight to carry is ", totalWeight, " and the volume used is ", totalVolume
END PROGRAM KNAPSACK</
Sample output
Maximum value achievable is 54500
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
=={{header|FreeBASIC}}==
{{trans|PureBASIC}}
<syntaxhighlight lang="vb">#define min(a, b) iif((a) < (b), (a), (b))
Dim As Single totalPeso, totalVolumen
Dim As Integer maxPanacea, maxIchor, maxGold, maxValor
Dim As Integer i, j ,k
Dim As Integer n(2)
Type Bounty
articulo As String*7
valor As Integer
peso As Single
volumen As Single
End Type
Dim item(1 To 5) As Bounty => { _
("panacea", 3000, 0.3, 0.025), ("ichor", 1800, 0.2, 0.015), _
("gold", 2500, 2.0, 0.002), ("sack", 0, 25.0, 0.25 )}
maxPanacea = min(item(4).peso/item(1).peso, item(4).volumen/item(1).volumen)
maxIchor = min(item(4).peso/item(2).peso, item(4).volumen/item(2).volumen)
maxGold = min(item(4).peso/item(3).peso, item(4).volumen/item(3).volumen)
For i = 0 To maxPanacea
For j = 0 To maxIchor
For k = 0 To maxGold
item(0).valor = k*item(3).valor + j*item(2).valor + i*item(1).valor
item(0).peso = k*item(3).peso + j*item(2).peso + i*item(1).peso
item(0).volumen = k*item(3).volumen + j*item(2).volumen + i*item(1).volumen
If item(0).peso > item(4).peso Or item(0).volumen > item(4).volumen Then
Continue For
End If
If item(0).valor > maxValor Then
maxValor = item(0).valor
totalPeso = item(0).peso
totalVolumen = item(0).volumen
n(0) = i: n(1) = j: n(2) = k
End If
Next k
Next j
Next i
Print "Maximum valor achievable is "; Str(maxValor)
Print "This is achieved by carrying "; Str(n(0));
Print " panacea, "; Str(n(1)); " ichor and "; Str(n(2)); " gold items."
Print "The peso to carry is "; Str(totalPeso);
Print " and the volume used is "; Str(totalVolumen)
Sleep</syntaxhighlight>
{{out}}
<pre>Maximum valor achievable is 54500
This is achieved by carrying 0 panacea, 15 ichor and 11 gold items
The peso to carry is 25 and the volume used is 0.247</pre>
=={{header|Go}}==
Recursive brute-force.
<
import "fmt"
Line 1,645 ⟶ 1,798:
fmt.Printf("TOTAL (%3d items) Weight: %4.1f Volume: %5.3f Value: %6d\n",
sumCount, sumWeight, sumVolume, sumValue)
}</
Output:
Line 1,657 ⟶ 1,810:
=={{header|Groovy}}==
Solution: dynamic programming
<
def totalVolume = { list -> list.collect{ it.item.volume * it.count }.sum() }
def totalValue = { list -> list.collect{ it.item.value * it.count }.sum() }
Line 1,680 ⟶ 1,833:
}
m[n][wm][vm]
}</
Test:
<
items.eachPermutation { itemList ->
def start = System.currentTimeMillis()
Line 1,703 ⟶ 1,856:
it.item.name, it.count, it.item.weight * it.count, it.item.volume * it.count)
}
}</
Output:
Line 1,753 ⟶ 1,906:
=={{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.
<
import Data.Ord (comparing)
Line 1,790 ⟶ 1,943:
main = putStr $ showOpt $ best options
where best = maximumBy $ comparing $ dotProduct vals</
Output:
Line 1,802 ⟶ 1,955:
=={{header|HicEst}}==
<
NN = ALIAS($Panacea, $Ichor, $Gold, wSack, wPanacea, wIchor, wGold, vSack, vPanacea, vIchor, vGold)
Line 1,829 ⟶ 1,982:
ENDDO
ENDDO
ENDDO</
<
value=54500; Panaceas=3; Ichors=10; Golds=11; weight=24.9; 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; </
=={{header|J}}==
Brute force solution.
<
prods=: <;. _1 ' panacea: ichor: gold:'
hdrs=: <;. _1 ' weight: volume: value:'
Line 1,854 ⟶ 2,007:
prtscr &.> hdrs ('total '&,@[,' ',":@])&.> mo ip"1 ws,vs,:vls
LF
)</
Example output:
<pre> KS''
Line 1,866 ⟶ 2,019:
=={{header|Java}}==
With recursion for more than 3 items.
<
import hu.pj.obj.Item;
Line 1,949 ⟶ 2,102:
} // main()
} // class</
<
public class Item {
Line 2,001 ⟶ 2,154:
}
} // class</
output:
Line 2,010 ⟶ 2,163:
=={{header|JavaScript}}==
Brute force.
<
panacea = { 'value': 3000, 'weight': 0.3, 'volume': 0.025 },
ichor = { 'value': 1800, 'weight': 0.2, 'volume': 0.015 },
Line 2,060 ⟶ 2,213:
(gold: 11, panacea: 3, ichor: 10)
(gold: 11, panacea: 6, ichor: 5)
(gold: 11, panacea: 9, ichor: 0)</pre></
=={{header|jq}}==
Line 2,067 ⟶ 2,220:
'''Works with gojq, the Go implementation of jq'''
<
{$name, $value, $weight, $volume};
Line 2,145 ⟶ 2,298:
f(.itemCount; .sumNumber; .bestValue; .sumWeight; .sumVolume) );
solve(25; 0.25)</
{{out}}
<pre>
Line 2,158 ⟶ 2,311:
=={{header|Julia}}==
{{libheader|JuMP}}<
using JuMP
using GLPKMathProgInterface
Line 2,181 ⟶ 2,334:
println("vials of panacea = ", getvalue(vials_of_panacea))
println("ampules of ichor = ", getvalue(ampules_of_ichor))
println("bars of gold = ", getvalue(bars_of_gold))</
{{output}}
<pre>
Line 2,202 ⟶ 2,355:
{{trans|C}}
Recursive brute force approach:
<
data class Item(val name: String, val value: Double, val weight: Double, val volume: Double)
Line 2,268 ⟶ 2,421:
print("${itemCount} items ${"%2d".format(sumNumber)} ${"%5.0f".format(bestValue)} ${"%4.1f".format(sumWeight)}")
println(" ${"%4.2f".format(sumVolume)}")
}</
{{out}}
Line 2,281 ⟶ 2,434:
=={{header|Lua}}==
<
["ichor"] = { ["value"] = 1800, ["weight"] = 0.2, ["volume"] = 0.015 },
["gold"] = { ["value"] = 2500, ["weight"] = 2.0, ["volume"] = 0.002 }
Line 2,316 ⟶ 2,469:
for k, v in pairs( best_amounts ) do
print( k, v )
end</
=={{header|MiniZinc}}==
<syntaxhighlight lang="minizinc">
%Knapsack problem/Unbounded. Nigel Galloway, August 13th., 2021
enum Items ={panacea,ichor,gold};
Line 2,328 ⟶ 2,481:
solve maximize sum(n in Items)(value[n]*take[n]);
output(["Take "++show(take[panacea])++" vials of panacea\nTake "++show(take[ichor])++" ampules of ichor\nTake "++ show(take[gold])++" bars of gold\n"])
</syntaxhighlight>
{{out}}
<pre>
Line 2,340 ⟶ 2,493:
=={{header|M4}}==
A brute force solution:
<
define(`set2d',`define(`$1[$2][$3]',`$4')')
define(`get2d',`defn(`$1[$2][$3]')')
Line 2,373 ⟶ 2,526:
')')
divert
mv best</
Output:
<pre>54500 (0,15,11) (3,10,11) (6,5,11) (9,0,11)</pre>
Line 2,379 ⟶ 2,532:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Brute force algorithm:
<
{iva,iwe,ivo}={1800,2/10,3/200};
{gva,gwe,gvo}={2500,2,2/1000};
Line 2,388 ⟶ 2,541:
data=Flatten[Table[{{p,i,g}.{pva,iva,gva},{p,i,g}.{pwe,iwe,gwe},{p,i,g}.{pvo,ivo,gvo},{p,i,g}},{p,0,pmax},{i,0,imax},{g,0,gmax}],2];
data=Select[data,#[[2]]<=25&&#[[3]]<=1/4&];
First[SplitBy[Sort[data,First[#1]>First[#2]&],First]]</
gives back an array of the best solution(s), with each element being value, weight, volume, {number of vials, number of ampules, number of bars}:
<
if we call the three items by their first letters the best packings are:
<
p:6 i:5 v:11
p:3 i:10 v:11
p:0 i:15 v:11</
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}}==
<
This model finds the integer optimal packing of a knapsack
Line 2,427 ⟶ 2,580:
;
end;</
The solution produced is at [[Knapsack problem/Unbounded/Mathprog]].
Line 2,433 ⟶ 2,586:
{{trans|Fortran}}
Note that unlike [[Fortran]] and [[C]], Modula-3 does not do any hidden casting, which is why <tt>FLOAT</tt> and <tt>FLOOR</tt> are used.
<
FROM IO IMPORT Put;
Line 2,479 ⟶ 2,632:
Put("This is achieved by carrying " & Int(n[1]) & " panacea, " & Int(n[2]) & " ichor and " & Int(n[3]) & " gold items\n");
Put("The weight of this carry is " & Real(totalWeight) & " and the volume used is " & Real(totalVolume) & "\n");
END Knapsack.</
Output:
<pre>Maximum value achievable is 54500
Line 2,488 ⟶ 2,641:
{{trans|Pascal}}
This is a brute-force solution translated from Pascal to Nim, which is straightforward.
<
import lenientops # Mixed float/int operators.
Line 2,525 ⟶ 2,678:
echo fmt"Maximum value achievable is {maxValue}."
echo fmt"This is achieved by carrying {n[1]} panacea, {n[2]} ichor and {n[3]} gold items."
echo fmt"The weight of this carry is {totalWeight:6.3f} and the volume used is {totalVolume:6.4f}."</
{{out}}
Line 2,536 ⟶ 2,689:
=={{header|OCaml}}==
This is a brute-force solution: it generates a list of every legal combination of items and then finds the best results:
<
let bounty n d w v = { name = n; value = d; weight = w; volume = v }
Line 2,611 ⟶ 2,764:
print_newline()
let () = List.iter print best_results</
outputs:
Line 2,656 ⟶ 2,809:
=={{header|Oz}}==
Using constraint propagation and branch and bound search:
<
proc {Knapsack Sol}
solution(panacea:P = {FD.decl}
Line 2,679 ⟶ 2,832:
{System.showInfo "\nResult:"}
{Show Best}
{System.showInfo "total value: "#{Value Best}}</
If you study the output, you see how the weight and volume equations automagically constrain the domain of the three variables.
Line 2,734 ⟶ 2,887:
=={{header|Pascal}}==
With ideas from C, Fortran and Modula-3.
<
uses
Line 2,787 ⟶ 2,940:
writeln ('This is achieved by carrying ', n[1], ' panacea, ', n[2], ' ichor and ', n[3], ' gold items');
writeln ('The weight of this carry is ', totalWeight:6:3, ' and the volume used is ', totalVolume:6:4);
end.</
Output:
<pre>:> ./Knapsack
Line 2,797 ⟶ 2,950:
=={{header|Perl}}==
Dynamic programming solution. Before you ask, no, it's actually slower for the given data set. See the alternate data set.
<
if (1) { # change 1 to 0 for different data set
Line 2,867 ⟶ 3,020:
$wtot/$wsc, $vtot/$vsc, $x->[0];
print "\nCache hit: $hits\tmiss: $misses\n";</
Output:<pre>Max value 54500, with:
Line 2,883 ⟶ 3,036:
For each goodie, fill yer boots, then (except for the last) recursively try with fewer and fewer.<br>
Increase profit and decrease weight/volume to pick largest profit for least weight and space.
<!--<
<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>
Line 2,928 ⟶ 3,081:
<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>
<!--</
{{out}}
<pre>
Line 2,936 ⟶ 3,089:
Profit 54500: 0 ichor, 9 panacea, 11 shiney shiney [weight:24.7, volume:0.247]
</pre>
=={{header|Picat}}==
This is a typical constraint modelling problem. We must use the MIP solver - using the mip module - for this problem since the data contains float values (which neither of the CP/SAT/SMT solvers support).
<syntaxhighlight lang="picat">import mip.
go =>
data(Items,Value,Weight,Volume,MaxWeight,MaxVolume),
knapsack_problem(Value,Weight,Volume,MaxWeight,MaxVolume, X,Z),
println(z=Z),
println(x=X),
N = Items.len,
foreach({Item,Num} in zip(Items,X), Num > 0)
printf("Take %d of %w\n", Num,Item)
end,
print("\nTotal volume: "),
println(sum([X[I]*Volume[I] : I in 1..N])),
print("Total weight: "),
println(sum([X[I]*Weight[I] : I in 1..N])),
print("Total cost: "),
println(sum([X[I]*Value[I] : I in 1..N])),
nl.
knapsack_problem(Value,Weight,Volume,MaxWeight,MaxVolume, X,Z) =>
println([max_weight=MaxWeight,max_volume=MaxVolume,z=Z]),
N = Value.length,
X = new_list(N),
X :: 0..1000,
Z #= sum([X[I]*Value[I] : I in 1..N]),
foreach(I in 1..N)
X[I] #>= 0
end,
limit(Weight, X, MaxWeight),
limit(Volume, X, MaxVolume),
if var(Z) then
println(maximize),
solve($[glpk,max(Z)], X)
else
solve($[glpk], X)
end.
limit(W, Take, WTMax) =>
sum([W[I]*Take[I] : I in 1..W.length]) #<= WTMax.
% data
data(Items,Value,Weight,Volume,MaxWeight,MaxVolume) =>
Items = ["panacea","ichor","gold"],
Value = [3000.0, 1800.0, 2500.0 ],
Weight = [ 0.3, 0.2, 2.0 ],
Volume = [ 0.025, 0.015, 0.002],
MaxWeight = 25.0,
MaxVolume = 0.25.</syntaxhighlight>
{{out}}
<pre>z = 54500
x = [9,0,11]
Take 9 of panacea
Take 11 of gold
Total volume: 0.247
Total weight: 24.699999999999999
Total cost: 54500.0</pre>
=={{header|PicoLisp}}==
Brute force solution
<
("panacea" 3 25 3000)
("ichor" 2 15 1800)
Line 2,962 ⟶ 3,187:
(inc 'N) )
(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)) )</
Output:
<pre> 15 x ichor 2 15 1800
Line 2,970 ⟶ 3,195:
=={{header|PowerShell}}==
{{works with|PowerShell|3.0}}
<
$Item = @(
[pscustomobject]@{ Name = 'panacea'; Unit = 'vials' ; value = 3000; Weight = 0.3; Volume = 0.025 }
Line 3,031 ⟶ 3,256:
# Show the results
$Solutions</
{{out}}
<pre>0 vials of panacea, 15 ampules of ichor, and 11 bars of gold worth a total of 54500.
Line 3,040 ⟶ 3,265:
=={{header|Prolog}}==
Works with SWI-Prolog and <b>library simplex</b> written by <b>Markus Triska</b>.
<
% tuples (name, Explantion, Value, weights, volume).
Line 3,125 ⟶ 3,350:
W2 is W1 + Wtemp,
Vo2 is Vo1 + Votemp ),
print_results(S, A0, A1, A2, A3, A4, T, TN, Va2, W2, Vo2).</
Output :
<pre> ?- knapsack.
Line 3,137 ⟶ 3,362:
=={{header|PureBasic}}==
{{trans|Fortran}}
<
Define.i maxPanacea, maxIchor, maxGold, maxValue
Define.i i, j ,k
Line 3,218 ⟶ 3,443:
Data.i 0
Data.f 25.0, 0.25
EndDataSection</
Outputs
Line 3,233 ⟶ 3,458:
=={{header|R}}==
Brute force method
<
weights <- c(panacea=0.3, ichor=0.2, gold=2.0)
volumes <- c(panacea=0.025, ichor=0.015, gold=0.002)
Line 3,254 ⟶ 3,479:
# Find the solutions with the highest value
vals <- apply(knapok, 1, getTotalValue)
knapok[vals == max(vals),]</
panacea ichor gold
2067 9 0 11
Line 3,264 ⟶ 3,489:
Using Dynamic Programming
<syntaxhighlight 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",
Line 3,353 ⟶ 3,578:
main_knapsack(Data_, 250, 250)
</syntaxhighlight>
<syntaxhighlight lang="r">
Output:
The Total profit is: 54500
You must carry: Gold (x 11 )
You must carry: Panacea (x 9 )
</syntaxhighlight>
=={{header|Racket}}==
<
#lang racket
Line 3,403 ⟶ 3,628:
(call-with-values (λ() (fill-sack items 0.25 25 '() 0))
(λ(sacks total) (for ([s sacks]) (display-sack s total))))
</syntaxhighlight>
{{out}}
Line 3,431 ⟶ 3,656:
Brute force, looked a lot at the Ruby solution.
<syntaxhighlight lang="raku"
has $.volume;
has $.weight;
Line 3,472 ⟶ 3,697:
say "maximum value is $max_val\npossible solutions:";
say "panacea\tichor\tgold";
.join("\t").say for @solutions;</
'''Output:'''
<pre>maximum value is 54500
Line 3,485 ⟶ 3,710:
{{trans|Fortran}}
===displays 1st solution===
<
/* value weight volume */
Line 3,521 ⟶ 3,746:
say left('', 40) "total weight: " maxW / 1
say left('', 40) "total volume: " maxV / 1
/*stick a fork in it, we're all done. */</
{{out|output|text= when using the internal default input:}}
<pre>
Line 3,535 ⟶ 3,760:
===displays all solutions===
<
maxPanacea= 0
Line 3,575 ⟶ 3,800:
say left('', 40) "total volume: " maxV.j / 1
end /*j*/
/*stick a fork in it, we're all done. */</
{{out|output|text= when using the internal default input:}}
<pre>
Line 3,621 ⟶ 3,846:
=={{header|Ruby}}==
Brute force method, {{trans|Tcl}}
<
panacea = KnapsackItem.new(0.025, 0.3, 3000)
ichor = KnapsackItem.new(0.015, 0.2, 1800)
Line 3,657 ⟶ 3,882:
i*ichor.weight + p*panacea.weight + g*gold.weight,
i*ichor.volume + p*panacea.volume + g*gold.volume
end</
{{out}}
<pre>
Line 3,668 ⟶ 3,893:
=={{header|SAS}}==
This is yet another brute force solution.
<
wtpanacea=0.3; wtichor=0.2; wtgold=2.0;
volpanacea=0.025; volichor=0.015; volgold=0.002;
Line 3,697 ⟶ 3,922:
proc print data=one (obs=4);
var panacea ichor gold vals;
run;</
Output:
<pre>
Line 3,709 ⟶ 3,934:
Use SAS/OR:
<
data mydata;
input Item $1-19 Value weight Volume;
Line 3,748 ⟶ 3,973:
print TotalValue;
for {s in 1.._NSOL_} print {i in ITEMS} NumSelected[i].sol[s];
quit;</
MILP solver output:
Line 3,787 ⟶ 4,012:
=={{header|Scala}}==
===Functional approach (Tail recursive)===
<
object UnboundedKnapsack extends App {
Line 3,824 ⟶ 4,049:
packer(items.map(i => Knapsack(Seq(i))), Nil).foreach(println)
}</
{{out}}
Line 3,836 ⟶ 4,061:
=={{header|Seed7}}==
<
include "float.s7i";
Line 3,886 ⟶ 4,111:
writeln("This is achieved by carrying " <& bestAmounts[1] <& " panacea, " <& bestAmounts[2] <& " ichor and " <& bestAmounts[3] <& " gold items");
writeln("The weight of this carry is " <& best.weight <& " and the volume used is " <& best.volume digits 4);
end func;</
Output:
Line 3,897 ⟶ 4,122:
=={{header|Sidef}}==
{{trans|Perl}}
<
Number volume,
Number weight,
Line 3,961 ⟶ 4,186:
#{"-" * 50}
Total:\t #{"%8d%8g%8d" % (wtot/wsc, vtot/vsc, x[0])}
EOT</
{{out}}
<pre>
Line 3,975 ⟶ 4,200:
=={{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 code quite legible:
<
proc main argv {
array set value {panacea 3000 ichor 1800 gold 2500}
Line 4,005 ⟶ 4,230:
puts "maxval: $maxval, best: $best"
}
main $argv</
<pre>$ time tclsh85 /Tcl/knapsack.tcl
Line 4,018 ⟶ 4,243:
filter them by the volume and weight restrictions, partition the remaining packings
by value, and search for the maximum value class.
<
#import flo
Line 4,031 ⟶ 4,256:
#cast %nmL
human_readable = ~&p/*<'panacea','ichor','gold'> solutions</
output:
<pre><
Line 4,045 ⟶ 4,270:
whilst the one below is focussing more on expressing/solving the problem
in less lines of code.
<
Sub Main()
Line 4,069 ⟶ 4,294:
If M(Value) = S(1)(Value) Then Debug.Print M(Value), M(Weight), M(Volume), M(PC), M(IC), M(GC)
Next
End Sub</
Output:<pre> Value Weight Volume PanaceaCount IchorCount GoldCount
54500 24.7 0.247 9 0 11
Line 4,080 ⟶ 4,305:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<
class Item {
Line 4,156 ⟶ 4,381:
System.print("----------- ------ ----- ------ ------")
Fmt.write("$d items $2d $5.0f $4.1f", itemCount, sumNumber, bestValue, sumWeight)
Fmt.print(" $4.2f", sumVolume)</
{{out}}
Line 4,166 ⟶ 4,391:
----------- ------ ----- ------ ------
2 items 20 54500 24.7 0.25
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">func Min(A, B);
real A, B;
return fix(if A < B then A else B);
int Panacea, Ichor, Gold, Panacea_, Ichor_, Gold_, Val, Max;
real Weight, Volume;
[Max:= 0;
for Panacea:= 0 to Min(25.0/0.3, 0.25/0.025) do
[for Ichor:= 0 to Min(25.0/0.2, 0.25/0.015) do
[for Gold:= 0 to Min(25.0/2.0, 0.25/0.002) do
[Val:= Panacea*3000 + Ichor*1800 + Gold*2500;
Weight:= float(Panacea)*0.3 + float(Ichor)*0.2 + float(Gold)*2.0;
Volume:= float(Panacea)*0.025 + float(Ichor)*0.015 + float(Gold)*0.002;
if Val>Max and Weight<=25.0 and Volume<= 0.25 then
[Max:= Val;
Panacea_:= Panacea; Ichor_:= Ichor; Gold_:= Gold;
];
];
];
];
Text(0, "The traveler carries ");
IntOut(0, Panacea_); Text(0, " vials of panacea, ");
IntOut(0, Ichor_); Text(0, " ampules of ichor, and ");
IntOut(0, Gold_); Text(0, " bars of gold"); CrLf(0);
Text(0, "for a maximum value of "); IntOut(0, Max); CrLf(0);
]</syntaxhighlight>
{{out}}
<pre>
The traveler carries 0 vials of panacea, 15 ampules of ichor, and 11 bars of gold
for a maximum value of 54500
</pre>
=={{header|zkl}}==
{{trans|D}}
<
ichor :=T(1800, 0.2, 0.015);
gold :=T(2500, 2.0, 0.002);
Line 4,190 ⟶ 4,448:
" %d panacea, %d ichor and %d gold").fmt(best[1].xplode()));
println("The weight to carry is %4.1f and the volume used is %5.3f"
.fmt(best[0][1,*].xplode()));</
cprod3 is the Cartesian product of three lists or iterators.
{{out}}
|