Knapsack problem/Continuous: Difference between revisions
m
→{{header|Wren}}: Minor tidy
No edit summary |
m (→{{header|Wren}}: Minor tidy) |
||
(8 intermediate revisions by 6 users not shown) | |||
Line 55:
{{trans|Python}}
<
(‘pork’, 5.4, 43.0),
(‘ham’, 3.6, 90.0),
Line 83:
print(‘ ITEM PORTION VALUE’)
print(bagged.map((n, p, a) -> ‘#10 #3.2 #3.2’.format(n, p, a)).join("\n"))
print("\nTOTAL WEIGHT: #2.2\nTOTAL VALUE: #2.2".format(wt, val))</
{{out}}
Line 99:
=={{header|Ada}}==
<
with Ada.Float_Text_IO;
with Ada.Strings.Unbounded;
Line 201:
end loop;
end Knapsack_Continuous;
</syntaxhighlight>
{{out}}
<pre>
Line 215:
=={{header|AWK}}==
<
BEGIN {
# arr["item,weight,price"]
Line 257:
exit(0)
}
</syntaxhighlight>
{{out}}
<pre>
Line 271:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
Sort% = FN_sortSAinit(1, 0) : REM Descending
Line 309:
PRINT '"Total weight = " ; TotalWeight " kg"
PRINT "Total price = " ; TotalPrice
END</
Output:
<pre>Take all the salami
Line 325:
The table of weights and prices are stored as strings to make them easier to edit. Two characters for the weight (with the decimal point dropped), two characters for the price, and then the name of the item. The total numbers of items (9) is specified by the first value on the stack.
<
>\`!v|:-1p\3\0p\2\+-*86g\3\*+55-*86g\2<<1v*g21\*g2<
nib@_>0022p6>12p:212gg48*:**012gg/\-:0`3^+>,,55+%6v
Line 339:
3767welt
3095salami
5998sausage</
{{out}}
Line 349:
=={{header|Bracmat}}==
<
The second argument is the number of decimals. }
= value decimals powerOf10
Line 398:
| out$(fixed$(!totalPrice.2))
)
);</
Output:<pre>3.5 kg of welt
2.4 kg of greaves
Line 407:
=={{header|C}}==
<
#include <stdlib.h>
Line 443:
return 0;
}</
take all salami
take all ham
Line 452:
=={{header|C sharp|C#}}==
<
class Program
{
Line 484:
static string[] items = {"beef","pork","ham","greaves","flitch",
"brawn","welt","salami","sausage"};
}</
Sorting three times is expensive,
an alternative is sorting once, with an indices array.
<
class Program
{
Line 519:
static string[] items = {"beef","pork","ham","greaves","flitch",
"brawn","welt","salami","sausage"};
}</
=={{header|C++}}==
<
#include<algorithm>
#include<string.h>
Line 616:
return 0;
}</
{{out}}
Line 631:
===Alternate Version===
<
#include <iostream>
#include <vector>
Line 683:
space -= item.weight;
}
}</
{{out}}
Line 695:
=={{header|Clojure}}==
<syntaxhighlight lang="clojure">
; Solve Continuous Knapsack Problem
; Nicolas Modrzyk
Line 744:
(rob items maxW)
</syntaxhighlight>
Output<pre>
Take all :salami
Line 755:
===Alternate Version===
<syntaxhighlight lang="clojure">
(def items
[{:name "beef" :weight 3.8 :price 36}
Line 780:
(rob items 15)
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(name nil :type string)
(weight nil :type real)
Line 810:
(make-item :name "sausage" :weight 5.9 :price 98))))
(loop for (name amount) in (knapsack items 15)
do (format t "~8A: ~,2F kg~%" name amount))))</
{{out}}
<pre>salami : 3.00 kg
Line 819:
=={{header|D}}==
<
struct Item {
Line 866:
writefln("%(%s\n%)", chosen);
Item("TOTAL", chosen.sumBy!"amount", chosen.sumBy!"value").writeln;
}</
{{out}}
<pre> ITEM AMOUNT VALUE $/unit
Line 877:
===Alternative Version===
<
import std.stdio, std.algorithm;
Line 902:
} else
return writefln("Take %.1fkg %s", left, it.item);
}</
{{out}}
<pre>Take all the salami
Line 909:
Take all the greaves
Take 3.5kg welt</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
{Structure to hold the data}
type TButcherInfo = record
Name: string;
Weight,Cost,PerKG: double;
end;
type PButcherInfo = ^TButcherInfo;
{Array of actual data}
var Items: array [0..8] of TButcherInfo =(
(Name: 'beef'; Weight: 3.8; Cost: 36.0),
(Name: 'pork'; Weight: 5.4; Cost: 43.0),
(Name: 'ham'; Weight: 3.6; Cost: 90.0),
(Name: 'greaves'; Weight: 2.4; Cost: 45.0),
(Name: 'flitch'; Weight: 4.0; Cost: 30.0),
(Name: 'brawn'; Weight: 2.5; Cost: 56.0),
(Name: 'welt'; Weight: 3.7; Cost: 67.0),
(Name: 'salami'; Weight: 3.0; Cost: 95.0),
(Name: 'sausage'; Weight: 5.9; Cost: 98.0)
);
function CompareButcher(List: TStringList; Index1, Index2: Integer): Integer;
{Compare routine to sort by Per Kilograph cost}
var Info1,Info2: TButcherInfo;
begin
Info1:=PButcherInfo(List.Objects[Index1])^;
Info2:=PButcherInfo(List.Objects[Index2])^;
Result:=Trunc(Info2.PerKG * 100 - Info1.PerKG * 100);
end;
procedure KnapsackProblem(Memo: TMemo);
{Solve the knapsack problem}
var SL: TStringList;
var I,Inx: integer;
var Info: TButcherInfo;
var Weight,Cost,Diff: double;
const Limit = 15;
begin
SL:=TStringList.Create;
try
{Calculate the per Kilogram cost for each item}
for I:=0 to High(Items) do
begin
Items[I].PerKG:=Items[I].Cost/Items[I].Weight;
SL.AddObject(Items[I].Name,@Items[I]);
end;
{Sort most expensive items to top of list}
SL.CustomSort(CompareButcher);
{Take the most expensive items }
Weight:=0; Cost:=0;
for I:=0 to SL.Count-1 do
begin
Info:=PButcherInfo(SL.Objects[I])^;
{Item exceeds the weight limit? }
if (Weight+Info.Weight)>=Limit then
begin
{Calculate percent to fill gap}
Diff:=(Limit-Weight)/Info.Weight;
{Save index}
Inx:=I;
break;
end
else
begin
{Add up totals}
Weight:=Weight+Info.Weight;
Cost:=Cost+Info.Cost;
end;
end;
{Display all items}
Memo.Lines.Add('Item Portion Value');
Memo.Lines.Add('--------------------------');
for I:=0 to Inx-1 do
begin
Info:=PButcherInfo(SL.Objects[I])^;
Memo.Lines.Add(Format('%-8s %8.2f %8.2f',[Info.Name,Info.Weight,Info.Cost]));
end;
Info:=PButcherInfo(SL.Objects[Inx])^;
{Calculate cost and weight to fill gap}
weight:=Weight+Info.Weight*Diff;
Cost:=Cost+Info.Cost*Diff;
{Display gap filling item}
Memo.Lines.Add(Format('%-8s %8.2f %8.2f',[Info.Name,Info.Weight*Diff,Info.Cost*Diff]));
Memo.Lines.Add('--------------------------');
Memo.Lines.Add(Format('Totals %8.2f %8.2f',[Weight,Cost]));
finally SL.Free; end;
end;
</syntaxhighlight>
{{out}}
<pre>
Item Portion Value
--------------------------
salami 3.00 95.00
ham 3.60 90.00
brawn 2.50 56.00
greaves 2.40 45.00
welt 3.50 63.38
--------------------------
Totals 15.00 349.38
Elapsed Time: 10.998 ms.
</pre>
=={{header|EchoLisp}}==
<
(lib 'struct)
(lib 'sql) ;; for table
Line 950 ⟶ 1,071:
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
CONTINUOUS_KNAPSACK
Line 1,025 ⟶ 1,146:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,038 ⟶ 1,159:
=={{header|Elixir}}==
{{trans|Erlang}}
<
def select( max_weight, items ) do
Enum.sort_by( items, fn {_name, weight, price} -> - price / weight end )
Line 1,073 ⟶ 1,194:
{"sausage", 5.9, 98} ]
KnapsackProblem.task( items, 15 )</
{{out}}
Line 1,087 ⟶ 1,208:
===Alternate Version===
{{trans|Ruby}}
<
def continuous(items, max_weight) do
Enum.sort_by(items, fn {_item, {weight, price}} -> -price / weight end)
Line 1,118 ⟶ 1,239:
sausage: {5.9, 98} ]
KnapsackProblem.continuous( items, 15 )</
{{out}}
Line 1,133 ⟶ 1,254:
=={{header|Erlang}}==
Note use of lists:foldr/2, since sort is ascending.
<syntaxhighlight lang="erlang">
-module( knapsack_problem_continuous ).
Line 1,170 ⟶ 1,291:
select_until_weight( Weight, Remains ) when Weight < Remains -> Weight;
select_until_weight( _Weight, Remains ) -> Remains.
</syntaxhighlight>
{{out}}
<pre>
Line 1,183 ⟶ 1,304:
=={{header|F_Sharp|F#}}==
<
//Fill a knapsack optimally - Nigel Galloway: February 1st., 2015
let items = [("beef", 3.8, 36);("pork", 5.4, 43);("ham", 3.6, 90);("greaves", 2.4, 45);("flitch" , 4.0, 30);("brawn", 2.5, 56);("welt", 3.7, 67);("salami" , 3.0, 95);("sausage", 5.9, 98)]
Line 1,201 ⟶ 1,322:
| [] -> printfn "Everything taken! Total value of swag is £%0.2f; Total weight of bag is %0.2fkg" a n
take(0.0, items, 0.0)
</syntaxhighlight>
{{out}}
<pre>
Line 1,230 ⟶ 1,351:
{{trans|D}}
{{works with|4tH|3.62.0}}
<
150 value left \ capacity in 1/10th kilo
Line 1,268 ⟶ 1,389:
;
knapsack</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
implicit none
Line 1,327 ⟶ 1,448:
write(*, "(f15.2, f8.2)") total_weight, total_value
end program KNAPSACK_CONTINUOUS</
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">#define PesoMax 15.0
Type Knapsack
articulo As String*7
peso As Double
precio As Double
End Type
'build item list
Dim item(1 To 9) As Knapsack => { _
("beef", 3.8, 36), ("pork", 5.4, 43), ("ham", 3.6, 90), _
("greaves", 2.4, 45), ("flitch", 4.0, 30), ("brawn", 2.5, 56), _
("welt", 3.7, 67), ("salami", 3.0, 95), ("sausage", 5.9, 98)}
Dim As Boolean Roba(Ubound(item))
Dim As Double PrecioXPeso(Ubound(item))
Dim As Integer i, MejorArticulo
Dim As Double Mejor, PesoArtic, TotalPeso = 0, TPeso = 0, TPrecio = 0, temp
For i = 1 To Ubound(item)
PrecioXPeso(i) = item(i).precio / item(i).peso
Roba(i) = False
Next i
Print "You can carry the following materials in the knapsack: "
Do
Mejor = 0
For i = 1 To Ubound(item)
If Not Roba(i) And PrecioXPeso(i) > Mejor Then
Mejor = PrecioXPeso(i)
MejorArticulo = i
End If
Next i
Roba(MejorArticulo) = True 'take item
PesoArtic = item(MejorArticulo).peso 'get its weight
TotalPeso += PesoArtic 'add to total weight
If TotalPeso > PesoMax Then 'if total is too much, reduce
PesoArtic -= TotalPeso - PesoMax 'item weight by amount it's over
End If
Print Using "##.# kg of "; PesoArtic; 'show weight and item
TPeso += PesoArtic
Print item(MejorArticulo).articulo;
temp = PesoArtic * item(MejorArticulo).precio / item(MejorArticulo).peso
TPrecio += temp
Print Chr(9); Using "(Value = ##.###)"; temp
Loop Until TotalPeso >= PesoMax 'all we can steal
Print !"\nMaximal weight:"; PesoMax; " kg"
Print Using "Total weight: ###.## kg"; TPeso
Print Using "Total value: ###.##"; TPrecio
Sleep</syntaxhighlight>
{{out}}
<pre>You can carry the following materials in the knapsack:
3.0 kg salami (Value = 95.000)
3.6 kg ham (Value = 90.000)
2.5 kg brawn (Value = 56.000)
2.4 kg greaves (Value = 45.000)
3.5 kg welt (Value = 63.378)
Maximal weight: 15 kg
Total weight: 15.00 kg
Total value: 349.38</pre>
=={{header|GNU APL}}==
<
Items←'beef' 'pork' 'ham' 'greaves' 'flitch' 'brawn' 'welt' 'salami' 'sausage'
Weights←3.8 5.4 3.6 2.4 4 2.5 3.7 3 5.9
Line 1,347 ⟶ 1,530:
⎕←''
⎕←'total cost:' TotalCost
</syntaxhighlight>
{{out}}
<pre>
Line 1,361 ⟶ 1,544:
=={{header|Go}}==
<
import (
Line 1,410 ⟶ 1,593:
}
}
}</
Output:
<pre>
Line 1,422 ⟶ 1,605:
=={{header|Groovy}}==
Solution: obvious greedy algorithm
<
def knapsackCont = { list, maxWeight = 15.0 ->
Line 1,440 ⟶ 1,623:
}
sack
}</
Test:
<
[name:'beef', weight:3.8, value:36],
[name:'pork', weight:5.4, value:43],
Line 1,459 ⟶ 1,642:
contents.each {
printf(" name: %-7s weight: ${it.weight} value: ${it.value}\n", it.name)
}</
Output:
Line 1,473 ⟶ 1,656:
We use a greedy algorithm.
<
import Data.Ord (comparing)
import Text.Printf (printf)
Line 1,521 ⟶ 1,704:
where
a = floor q
b = q - toEnum a</
{{Out}}
<pre>3 kg of salami
Line 1,531 ⟶ 1,714:
Or similar to above (but more succinct):
<
import Data.Ord (comparing)
import Text.Printf (printf)
Line 1,556 ⟶ 1,739:
| otherwise = printf "Take %.2f kg of the %s\n" (k :: Float) name
main = solution 15 items</
{{Out}}
<pre>Take all the salami
Line 1,566 ⟶ 1,749:
=={{header|Icon}} and {{header|Unicon}}==
This implements the greedy algorithm. This also uses a Unicon extension to ''reverse'' which reverses a list. In Icon, an IPL procedure is available to do the same.
<
procedure main()
Line 1,601 ⟶ 1,784:
item("salami", 3.0, 95),
item("sausage", 5.9, 98) ]
end</
{{libheader|Icon Programming Library}}
Line 1,617 ⟶ 1,800:
We take as much as we can of the most valuable items first, and continue until we run out of space. Only one item needs to be cut.
<
beef 3.8 36
pork 5.4 43
Line 1,631 ⟶ 1,814:
order=: \:prices%weights
take=: 15&<.&.(+/\) order{weights
result=: (*take)#(order{names),.' ',.":,.take</
This gives the result:
Line 1,641 ⟶ 1,824:
For a total value of:
<
349.378</
See [[Knapsack_problem/Continuous/J]] for some comments on intermediate results...
Line 1,649 ⟶ 1,832:
Greedy solution.
<
package hu.pj.alg.test;
Line 1,722 ⟶ 1,905:
}
} // class</
<
package hu.pj.alg;
Line 1,800 ⟶ 1,983:
}
} // class</
<
package hu.pj.obj;
Line 1,861 ⟶ 2,044:
}
} // class</
output:
Line 1,879 ⟶ 2,062:
{{ works with|jq|1.4}}
<
# an array of objects {"name": _, "weight": _, "value": _}
# where "value" is the value of the given weight of the object.
Line 1,900 ⟶ 2,083:
| (.[] | {name, weight}),
"Total value: \( map(.value) | add)",
"Total weight: \(W - $remainder)" ;</
'''The task:'''
<
{ "name": "beef", "weight": 3.8, "value": 36},
{ "name": "pork", "weight": 5.4, "value": 43},
Line 1,913 ⟶ 2,096:
{ "name": "sausage", "weight": 5.9, "value": 98} ];
items | continuous_knapsack(15)</
{{out}}
<
{"name":"salami","weight":3}
{"name":"ham","weight":3.6}
Line 1,922 ⟶ 2,105:
{"name":"welt","weight":3.5000000000000004}
Total value: 349.3783783783784
Total weight: 15</
=={{header|Julia}}==
Line 1,930 ⟶ 2,113:
'''Type and Functions''':
<
struct KPCSupply{T<:Real}
Line 1,961 ⟶ 2,144:
end
return sack
end</
'''Main''':
<
KPCSupply("pork", 54//10, 43),
KPCSupply("ham", 36//10, 90),
Line 1,977 ⟶ 2,160:
println("The store contains:\n - ", join(store, "\n - "))
println("\nThe thief should take::\n - ", join(sack, "\n - "))
@printf("\nTotal value in the sack: %.2f €\n", sum(getfield.(sack, :value)))</
{{out}}
Line 2,001 ⟶ 2,184:
=={{header|Kotlin}}==
<
data class Item(val name: String, val weight: Double, val value: Double)
Line 2,047 ⟶ 2,230:
println("----------- ------ ------")
println("${itemCount} items 15.0 ${"%6.2f".format(sumValue)}")
}</
{{out}}
Line 2,066 ⟶ 2,249:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Knapsack {
Form 60, 40
Line 2,148 ⟶ 2,331:
}
Knapsack
</syntaxhighlight>
Output the same as other examples, with some color.
Line 2,156 ⟶ 2,339:
The output is then all items prior to this one, along with that item corrected for it's excess weighter (overW)
<
sortedTable = SortBy[{#1, #2, #3, #3/#2} & @@@ shop, -#[[4]] &];
overN = Position[Accumulate[sortedTable[[1 ;;, 2]]], a_ /; a > capacity, 1,1][[1, 1]];
Line 2,164 ⟶ 2,347:
output[[-1, 2]] = output[[-1, 2]] - overW;
output[[-1, 3]] = output[[-1, 2]] output[[-1, 4]];
Append[output[[1 ;;, 1 ;; 3]], {"Total",Sequence @@ Total[output[[1 ;;, 2 ;; 3]]]}]]</
A test using the specified data:
<
{{"beef", 3.8, 36}, {"pork", 5.4, 43}, {"ham", 3.6, 90}, {"greaves", 2.4, 45}, {"flitch", 4., 30},
{"brawn", 2.5, 56}, {"welt", 3.7, 67}, {"salami", 3., 95}, {"sausage", 5.9, 98}};
Line 2,179 ⟶ 2,362:
welt 3.5 63.3784
Total 15. 349.378
</syntaxhighlight>
=={{header|Mathprog}}==
<syntaxhighlight lang="text">/*Knapsack
This model finds the optimal packing of a knapsack
Line 2,212 ⟶ 2,395:
sausage 5.9 98
;
end;</
The solution is here at [[Knapsack problem/Continuous/Mathprog]].
=={{header|MiniZinc}}==
<syntaxhighlight lang="minizinc">
%Knapsack Continuous. Nigel Galloway: October 7th., 2020.
enum Items={beef,pork,ham,greaves,flitch,brawn,welt,salami,sausage};
Line 2,229 ⟶ 2,412:
solve maximize wValue;
output[concat([let {string: g=show(quantity[n])} in "Take "++(if g==show(weight[n]) then "all" else g endif)++" of \(n)\n" | n in Items where show(quantity[n])!="0.0"])++"\nTotal Weight=\(wTaken) Total Value="++show_float(4,2,wValue)]
</syntaxhighlight>
{{out}}
<pre>
Line 2,241 ⟶ 2,424:
</pre>
=={{header|Nim}}==
<
import strformat
Line 2,278 ⟶ 2,461:
break
echo fmt"Total value: {value:.2f}"</
{{out}}
Line 2,291 ⟶ 2,474:
=={{header|OCaml}}==
<
[ "beef", 3.8, 36;
"pork", 5.4, 43;
Line 2,324 ⟶ 2,507:
Printf.printf " %7s: %6.2f %6.2f\n" last rem_weight last_price;
Printf.printf " Total Price: %.3f\n" (float price +. last_price);
;;</
{{out}}
Line 2,338 ⟶ 2,521:
=={{header|Oforth}}==
<
[ "beef", 3.8, 36 ], [ "pork", 5.4, 43 ], [ "ham", 3.6, 90 ],
[ "greaves", 2.4, 45 ], [ "flitch", 4.0, 30 ], [ "brawn", 2.5, 56 ],
Line 2,355 ⟶ 2,538:
"And part of" . item first . " :" . dup .cr
item third * item second / value + "Total value :" . .cr break
] ;</
{{out}}
Line 2,371 ⟶ 2,554:
=={{header|ooRexx}}==
===version 1===
<
* 20.09.2014 Walter Pachl translated from REXX version 2
* utilizing ooRexx features like objects, array(s) and sort
Line 2,445 ⟶ 2,628:
Otherwise res='-1'
End
Return res</
{{out}}
<pre>
Line 2,468 ⟶ 2,651:
total 15.000 349.378</pre>
===version 2===
<
* 20.09.2014 Walter Pachl translated from REXX version 2
* utilizing ooRexx features like objects, array(s) and sort
Line 2,540 ⟶ 2,723:
Expose vpu
use Arg other
return -sign(vpu - other~vpu)</
Output is the same as for version 1.
=={{header|Pascal}}==
{{works with|FPC}}
For a continuous version of the knapsack problem, the greedy approach provides an optimal solution.
<syntaxhighlight lang="pascal">
program Knapsack;
{$mode delphi}
uses
SysUtils, Math, Generics.Collections, Generics.Defaults;
type
TItem = record
Name: string;
Weight, Value, Price: Double;
constructor Make(const n: string; w, v: Double);
end;
constructor TItem.Make(const n: string; w, v: Double);
begin
Name := n;
Weight := w;
Value := v;
Price := v/w;
end;
function ItemCmp(constref L, R: TItem): Integer;
begin
Result := CompareValue(R.Price, L.Price);
end;
var
Items: array of TItem;
MaxWeight: Double;
I: Integer;
begin
Items := [
TItem.Make('beef', 3.8, 36),
TItem.Make('pork', 5.4, 43),
TItem.Make('ham', 3.6, 90),
TItem.Make('greaves', 2.4, 45),
TItem.Make('flitch', 4.0, 30),
TItem.Make('brawn', 2.5, 56),
TItem.Make('welt', 3.7, 67),
TItem.Make('salami', 3.0, 95),
TItem.Make('sausage', 5.9, 98)
];
TArrayHelper<TItem>.Sort(Items, TComparer<TItem>.Construct(ItemCmp));
MaxWeight := 15.0;
I := 0;
repeat
Items[I].Weight := Min(Items[I].Weight, MaxWeight);
MaxWeight := MaxWeight - Items[I].Weight;
WriteLn(Format('%-8s %.1f kg', [Items[I].Name, Items[I].Weight]));
Inc(I);
until (MaxWeight <= 0)or(I = Length(Items));
end.
</syntaxhighlight>
{{out}}
<pre>
salami 3.0 kg
ham 3.6 kg
brawn 2.5 kg
greaves 2.4 kg
welt 3.5 kg
</pre>
=={{header|Perl}}==
<
(
[qw'beef 3.8 36'],
Line 2,574 ⟶ 2,822:
print "-" x 40, "\ntotal value: $value\n";
</syntaxhighlight>
Output:<pre>item fraction weight value
salami all 3.0 95
Line 2,586 ⟶ 2,834:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">meats</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span>
Line 2,618 ⟶ 2,866:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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;">"Total value: %f\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">worth</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
<pre>
Line 2,630 ⟶ 2,878:
=={{header|PHP}}==
<
$data = [
[
Line 2,694 ⟶ 2,942:
$limit -= $item['weight'];
endforeach;
</syntaxhighlight>
Output:
<pre>Take all the salami
Line 2,701 ⟶ 2,949:
Take all the greaves
Take 3.5 kg of welt</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">go =>
items(Items),
weights(Weights),
values(Values),
knapsack_max_weight(MaxWeight),
knapsack(Weights,Values,MaxWeight, X,TotalWeight,TotalValue),
nl,
printf("Total weight: %0.2f Total value: %0.2f\n", TotalWeight,TotalValue),
foreach(I in 1..Items.len)
if X[I] > 0.0 then
printf("%-8w: ",Items[I]),
if X[I] == Weights[I] then
printf("%0.2f (%w)", Weights[I], all)
else
printf("%-0.2f",X[I])
end,
nl
end
end,
nl.
knapsack(Weights,Values,MaxWeight, X,TotalWeight,TotalValue) =>
N = Weights.len,
X = new_list(N),
X :: 0.0..max(Weights),
TotalWeight #= sum(X),
TotalWeight #<= MaxWeight,
foreach(I in 1..N)
X[I] #<= Weights[I]
end,
WeightsInv = [1/Weights[I] : I in 1..N],
TotalValue #= sum([X[I]*Values[I]*WeightsInv[I] : I in 1..N]),
Vars = X ++ [TotalWeight],
solve($[glpk,max(TotalValue)],Vars).
% data
knapsack_max_weight(15.0).
items([beef,pork,ham,greaves,flitch,brawn,welt,salami,sausage]).
weights([3.8,5.4,3.6,2.4,4.0,2.5,3.7,3.0,5.9]).
values([36,43,90,45,30,56,67,95,98]).</syntaxhighlight>
{{out}}
<pre>otal weight: 15.00 Total value: 349.38
ham : 3.60 (all)
greaves : 2.40 (all)
brawn : 2.50 (all)
welt : 3.50
salami : 3.00</pre>
=={{header|PicoLisp}}==
<
(de *Items
Line 2,735 ⟶ 3,040:
NIL
(format (sum cadr K) *Scl)
(format (sum caddr K) *Scl) ) )</
Output:
<pre> salami 3.00 95.00
Line 2,745 ⟶ 3,050:
=={{header|PL/I}}==
<
KNAPSACK_CONTINUOUS: Proc Options(main);
/*--------------------------------------------------------------------
Line 2,819 ⟶ 3,124:
item(i).value = value;
End;
End;</
{{out}}
<pre>
Line 2,843 ⟶ 3,148:
=={{header|Prolog}}==
Works with SWI-Prolog and <b>library(simplex)</b> written by <b>Markus Triska</b>
<
% tuples (name, weights, value).
knapsack :-
Line 2,909 ⟶ 3,214:
print_results(S, A1, A2, A3, T, TN, W2, V2).
</syntaxhighlight>
Output :
<pre> ?- knapsack.
Line 2,922 ⟶ 3,227:
=={{header|PureBasic}}==
Using the greedy algorithm.
<
name.s
weight.f ;units are kilograms (kg)
Line 2,993 ⟶ 3,298:
Input()
CloseConsole()
EndIf </
Sample output:
<pre>Maximal weight = 15 kg
Line 3,008 ⟶ 3,313:
=={{header|Python}}==
I think this greedy algorithm of taking the largest amounts of items ordered by their value per unit weight is maximal:
<
items = [("beef", 3.8, 36.0),
("pork", 5.4, 43.0),
Line 3,037 ⟶ 3,342:
print(" ITEM PORTION VALUE")
print("\n".join("%10s %6.2f %6.2f" % item for item in bagged))
print("\nTOTAL WEIGHT: %5.2f\nTOTAL VALUE: %5.2f" % (wt, val))</
'''Sample Output'''
Line 3,052 ⟶ 3,357:
=={{header|R}}==
Translated into r-script by Shana White (vandersm@mail.uc.edu) from pseudocode found in 'Algorithms: Sequential Parallel and Distributed', by Kenneth A. Berman and Jerome L. Paul
<syntaxhighlight lang="r">
knapsack<- function(Value, Weight, Objects, Capacity){
Fraction = rep(0, length(Value))
Line 3,095 ⟶ 3,400:
print("Total value of tasty meats:")
print(Total_Value)
}</
'''Sample Input'''
Line 3,116 ⟶ 3,421:
=={{header|Racket}}==
<
(define shop-inventory
'((beef 3.8 36)
Line 3,160 ⟶ 3,465:
(call-with-values (lambda () (continuous-knapsack shop-inventory null 15 0))
report-knapsack)</
{{out}}
Line 3,175 ⟶ 3,480:
{{works with|rakudo|2015-09-16}}
This Solutions sorts the item by WEIGHT/VALUE
<syntaxhighlight lang="raku"
has $.name;
has $.weight is rw;
Line 3,218 ⟶ 3,523:
$max-w -= .weight;
last if $last-one;
}</
'''Output:'''
<pre>Item Portion Value
Line 3,231 ⟶ 3,536:
Originally used the Fortran program as a prototype.
<br>Some amount of code was added to format the output better.
<
@.= /*═══════ name weight value ══════*/
@.1 = 'flitch 4 30 '
Line 3,272 ⟶ 3,577:
syf: call sy arg(1), $(format(arg(2), , d)), $(format(arg(3), , d)); return
title: call sy center('item',nL), center("weight", wL), center('value', vL); return
$: parse arg x;if pos(.,x)>1 then x=left(strip(strip(x,'T',0),,.),length(x)); return x</
'''output''' using the default inputs of: <tt> 15 3 </tt>
<pre>
Line 3,306 ⟶ 3,611:
===version 2===
<
* 19.09.2014 Walter Pachl translated from FORTRAN
* While this program works with all REXX interpreters,
Line 3,382 ⟶ 3,687:
input.i=name'*'weight'*'value
input.0=i
Return</
{{out}}
<pre># vpu name weight value
Line 3,405 ⟶ 3,710:
=={{header|Ruby}}==
<
[:pork , 5.4, 43],
[:ham , 3.6, 90],
Line 3,424 ⟶ 3,729:
break
end
end</
{{out}}
<pre>
Line 3,438 ⟶ 3,743:
=={{header|Run BASIC}}==
{{incorrect|Run BASIC}}
<
dim wgt(9)
dim price(9)
Line 3,494 ⟶ 3,799:
print "-------- Total ";using("###.#",totTake);chr$(9);"Weight: ";totWgt
end if
next i</
<pre>Best 2 Options
Line 3,505 ⟶ 3,810:
=={{header|Rust}}==
<
let items: [(&str, f32, u8); 9] = [
("beef", 3.8, 36),
Line 3,538 ⟶ 3,843:
}
}
}</
Grab 3.0 kgs of salami
Grab 3.6 kgs of ham
Line 3,548 ⟶ 3,853:
=={{header|SAS}}==
Use LP solver in SAS/OR:
<
data mydata;
input item $ weight value;
Line 3,583 ⟶ 3,888:
print TotalValue;
print {i in ITEMS: WeightSelected[i].sol > 1e-3} WeightSelected;
quit;</
Output:
Line 3,598 ⟶ 3,903:
=={{header|Scala}}==
===Functional approach (Tail recursive)===
<
object ContinousKnapsackForRobber extends App {
Line 3,654 ⟶ 3,959:
println(packer(sortedItems, Lootsack(Nil)))
}</
{{Out}}
<pre>100.00% Salami 3.0 95.00
Line 3,666 ⟶ 3,971:
=={{header|Sidef}}==
{{trans|Perl}}
<
[
[:beef, 3.8, 36],
Line 3,695 ⟶ 4,000:
}
say "#{'-'*28}\ntotal value: #{'%.14g' % value }"</
{{out}}
<pre>
Line 3,709 ⟶ 4,014:
=={{header|Tcl}}==
<
# Uses the trivial greedy algorithm
Line 3,745 ⟶ 4,050:
# We return the total value too, purely for convenience
return [list $result $totalValue]
}</
Driver for this particular problem:
<
{beef 3.8 36}
{pork 5.4 43}
Line 3,765 ⟶ 4,070:
lassign $item name mass value
puts [format "\t%.1fkg of %s, value %.2f" $mass $name $value]
}</
Output:
<pre>
Line 3,782 ⟶ 4,087:
[http://www.gnu.org/software/glpk/glpk.html glpk] depending on the
[http://www.basis.netii.net/avram run-time system] configuration).
<
#import lin
Line 3,808 ⟶ 4,113:
#cast %em
main = solution system items</
output:
<pre><
Line 3,817 ⟶ 4,122:
'welt ': 3.500000e+00></pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="v (vlang)">struct Item {
item string
weight f64
Line 3,859 ⟶ 4,164:
}
//println(items)
}</
{{out}}
<pre>
Line 3,874 ⟶ 4,179:
{{libheader|Wren-math}}
{{libheader|Wren-sort}}
<
import "./math" for Math
import "./sort" for Sort
class Item {
Line 3,927 ⟶ 4,232:
}
System.print("----------- ------ ------")
Fmt.print("$d items 15.0 $6.2f", itemCount, sumValue)</
{{out}}
Line 3,943 ⟶ 4,248:
=={{header|XPL0}}==
<
real Weight, Best, ItemWt, TotalWt;
def Items = 9;
Line 3,972 ⟶ 4,277:
Text(0, Name(BestItem)); CrLf(0);
until TotalWt >= 15.0; \all we can steal
]</
Output:
Line 3,985 ⟶ 4,290:
=={{header|zkl}}==
{{trans|C}}
<
T(3.6, 90.0, "ham"), T(2.4, 45.0, "greaves"),
T(4.0, 30.0, "flitch"),T(2.5, 56.0, "brawn"),
Line 3,998 ⟶ 4,303:
if (space >= w){ println("take all ",nm); space-=w }
else{ println("take %gkg of %gkg of %s".fmt(space,w,nm)); break }
}</
{{out}}
<pre>
|