Knapsack problem/Continuous: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(Added PHP code) |
m (→{{header|Wren}}: Minor tidy) |
||
(15 intermediate revisions by 13 users not shown) | |||
Line 51:
* Wikipedia article: [[wp:Continuous_knapsack_problem|continuous knapsack]].
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V items = [(‘beef’, 3.8, 36.0),
(‘pork’, 5.4, 43.0),
(‘ham’, 3.6, 90.0),
(‘greaves’, 2.4, 45.0),
(‘flitch’, 4.0, 30.0),
(‘brawn’, 2.5, 56.0),
(‘welt’, 3.7, 67.0),
(‘salami’, 3.0, 95.0),
(‘sausage’, 5.9, 98.0)]
V MAXWT = 15.0
V sorted_items = sorted(items.map((name, amount, value) -> (value / amount, amount, name)), reverse' 1B)
V wt = 0.0
V val = 0.0
[(String, Float, Float)] bagged
L(unit_value, amount, name) sorted_items
V portion = min(MAXWT - wt, amount)
wt += portion
V addval = portion * unit_value
val += addval
bagged [+]= (name, portion, addval)
I wt >= MAXWT
L.break
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))</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
TOTAL WEIGHT: 15.00
TOTAL VALUE: 349.38
</pre>
=={{header|Ada}}==
<
with Ada.Float_Text_IO;
with Ada.Strings.Unbounded;
Line 155 ⟶ 201:
end loop;
end Knapsack_Continuous;
</syntaxhighlight>
{{out}}
<pre>
Line 169 ⟶ 215:
=={{header|AWK}}==
<
BEGIN {
# arr["item,weight,price"]
Line 211 ⟶ 257:
exit(0)
}
</syntaxhighlight>
{{out}}
<pre>
Line 225 ⟶ 271:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
Sort% = FN_sortSAinit(1, 0) : REM Descending
Line 263 ⟶ 309:
PRINT '"Total weight = " ; TotalWeight " kg"
PRINT "Total price = " ; TotalPrice
END</
Output:
<pre>Take all the salami
Line 279 ⟶ 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 293 ⟶ 339:
3767welt
3095salami
5998sausage</
{{out}}
Line 303 ⟶ 349:
=={{header|Bracmat}}==
<
The second argument is the number of decimals. }
= value decimals powerOf10
Line 352 ⟶ 398:
| out$(fixed$(!totalPrice.2))
)
);</
Output:<pre>3.5 kg of welt
2.4 kg of greaves
Line 361 ⟶ 407:
=={{header|C}}==
<
#include <stdlib.h>
Line 397 ⟶ 443:
return 0;
}</
take all salami
take all ham
Line 406 ⟶ 452:
=={{header|C sharp|C#}}==
<
class Program
{
Line 438 ⟶ 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 473 ⟶ 519:
static string[] items = {"beef","pork","ham","greaves","flitch",
"brawn","welt","salami","sausage"};
}</
=={{header|C++}}==
<
#include<algorithm>
#include<string.h>
Line 570 ⟶ 616:
return 0;
}</
{{out}}
Line 585 ⟶ 631:
===Alternate Version===
<
#include <iostream>
#include <vector>
Line 637 ⟶ 683:
space -= item.weight;
}
}</
{{out}}
Line 649 ⟶ 695:
=={{header|Clojure}}==
<syntaxhighlight lang="clojure">
; Solve Continuous Knapsack Problem
; Nicolas Modrzyk
Line 698 ⟶ 744:
(rob items maxW)
</syntaxhighlight>
Output<pre>
Take all :salami
Line 709 ⟶ 755:
===Alternate Version===
<syntaxhighlight lang="clojure">
(def items
[{:name "beef" :weight 3.8 :price 36}
Line 734 ⟶ 780:
(rob items 15)
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(name nil :type string)
(weight nil :type real)
Line 764 ⟶ 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 773 ⟶ 819:
=={{header|D}}==
<
struct Item {
Line 820 ⟶ 866:
writefln("%(%s\n%)", chosen);
Item("TOTAL", chosen.sumBy!"amount", chosen.sumBy!"value").writeln;
}</
{{out}}
<pre> ITEM AMOUNT VALUE $/unit
Line 831 ⟶ 877:
===Alternative Version===
<
import std.stdio, std.algorithm;
Line 856 ⟶ 902:
} else
return writefln("Take %.1fkg %s", left, it.item);
}</
{{out}}
<pre>Take all the salami
Line 863 ⟶ 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 904 ⟶ 1,071:
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
CONTINUOUS_KNAPSACK
Line 979 ⟶ 1,146:
end
</syntaxhighlight>
{{out}}
<pre>
Line 992 ⟶ 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,027 ⟶ 1,194:
{"sausage", 5.9, 98} ]
KnapsackProblem.task( items, 15 )</
{{out}}
Line 1,041 ⟶ 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,072 ⟶ 1,239:
sausage: {5.9, 98} ]
KnapsackProblem.continuous( items, 15 )</
{{out}}
Line 1,087 ⟶ 1,254:
=={{header|Erlang}}==
Note use of lists:foldr/2, since sort is ascending.
<syntaxhighlight lang="erlang">
-module( knapsack_problem_continuous ).
Line 1,124 ⟶ 1,291:
select_until_weight( Weight, Remains ) when Weight < Remains -> Weight;
select_until_weight( _Weight, Remains ) -> Remains.
</syntaxhighlight>
{{out}}
<pre>
Line 1,137 ⟶ 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,155 ⟶ 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,184 ⟶ 1,351:
{{trans|D}}
{{works with|4tH|3.62.0}}
<
150 value left \ capacity in 1/10th kilo
Line 1,222 ⟶ 1,389:
;
knapsack</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
implicit none
Line 1,281 ⟶ 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,301 ⟶ 1,530:
⎕←''
⎕←'total cost:' TotalCost
</syntaxhighlight>
{{out}}
<pre>
Line 1,315 ⟶ 1,544:
=={{header|Go}}==
<
import (
Line 1,364 ⟶ 1,593:
}
}
}</
Output:
<pre>
Line 1,376 ⟶ 1,605:
=={{header|Groovy}}==
Solution: obvious greedy algorithm
<
def knapsackCont = { list, maxWeight = 15.0 ->
Line 1,394 ⟶ 1,623:
}
sack
}</
Test:
<
[name:'beef', weight:3.8, value:36],
[name:'pork', weight:5.4, value:43],
Line 1,413 ⟶ 1,642:
contents.each {
printf(" name: %-7s weight: ${it.weight} value: ${it.value}\n", it.name)
}</
Output:
Line 1,427 ⟶ 1,656:
We use a greedy algorithm.
<
import Data.Ord (comparing)
import Text.Printf (printf)
Line 1,475 ⟶ 1,704:
where
a = floor q
b = q - toEnum a</
{{Out}}
<pre>3 kg of salami
Line 1,485 ⟶ 1,714:
Or similar to above (but more succinct):
<
import Data.Ord (comparing)
import Text.Printf (printf)
Line 1,510 ⟶ 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,520 ⟶ 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,555 ⟶ 1,784:
item("salami", 3.0, 95),
item("sausage", 5.9, 98) ]
end</
{{libheader|Icon Programming Library}}
Line 1,571 ⟶ 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,585 ⟶ 1,814:
order=: \:prices%weights
take=: 15&<.&.(+/\) order{weights
result=: (*take)#(order{names),.' ',.":,.take</
This gives the result:
Line 1,595 ⟶ 1,824:
For a total value of:
<
349.378</
See [[Knapsack_problem/Continuous/J]] for some comments on intermediate results...
Line 1,603 ⟶ 1,832:
Greedy solution.
<
package hu.pj.alg.test;
Line 1,676 ⟶ 1,905:
}
} // class</
<
package hu.pj.alg;
Line 1,754 ⟶ 1,983:
}
} // class</
<
package hu.pj.obj;
Line 1,815 ⟶ 2,044:
}
} // class</
output:
Line 1,833 ⟶ 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,854 ⟶ 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,867 ⟶ 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,876 ⟶ 2,105:
{"name":"welt","weight":3.5000000000000004}
Total value: 349.3783783783784
Total weight: 15</
=={{header|Julia}}==
Line 1,884 ⟶ 2,113:
'''Type and Functions''':
<
struct KPCSupply{T<:Real}
Line 1,915 ⟶ 2,144:
end
return sack
end</
'''Main''':
<
KPCSupply("pork", 54//10, 43),
KPCSupply("ham", 36//10, 90),
Line 1,931 ⟶ 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 1,955 ⟶ 2,184:
=={{header|Kotlin}}==
<
data class Item(val name: String, val weight: Double, val value: Double)
Line 2,001 ⟶ 2,230:
println("----------- ------ ------")
println("${itemCount} items 15.0 ${"%6.2f".format(sumValue)}")
}</
{{out}}
Line 2,020 ⟶ 2,249:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Knapsack {
Form 60, 40
Line 2,102 ⟶ 2,331:
}
Knapsack
</syntaxhighlight>
Output the same as other examples, with some color.
=={{header|Mathematica}}/{{header|Wolfram Language}}==
The problem is solved by sorting the original table by price to weight ratio, finding the accumlated weight, and the index of the item which exedes the carrying capacity (overN)
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,118 ⟶ 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,133 ⟶ 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,166 ⟶ 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,183 ⟶ 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,195 ⟶ 2,424:
</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import algorithm
import strformat
Line 2,234 ⟶ 2,461:
break
echo fmt"Total value: {value:.2f}"</syntaxhighlight>
{{out}}
Line 2,248 ⟶ 2,474:
=={{header|OCaml}}==
<
[ "beef", 3.8, 36;
"pork", 5.4, 43;
Line 2,281 ⟶ 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,295 ⟶ 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,312 ⟶ 2,538:
"And part of" . item first . " :" . dup .cr
item third * item second / value + "Total value :" . .cr break
] ;</
{{out}}
Line 2,328 ⟶ 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,402 ⟶ 2,628:
Otherwise res='-1'
End
Return res</
{{out}}
<pre>
Line 2,425 ⟶ 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,497 ⟶ 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,531 ⟶ 2,822:
print "-" x 40, "\ntotal value: $value\n";
</syntaxhighlight>
Output:<pre>item fraction weight value
salami all 3.0 95
Line 2,543 ⟶ 2,834:
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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>
<span style="color: #000080;font-style:italic;">--Item Weight (kg) Price (Value)</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"beef"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3.8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"pork"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5.4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">43</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"ham"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3.6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">90</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"greaves"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2.4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">45</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"flitch"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4.0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">30</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"brawn"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">56</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"welt"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3.7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"salami"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3.0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">95</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"sausage"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5.9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">98</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">by_weighted_value</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{?,</span><span style="color: #000000;">weighti</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pricei</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">meats</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span>
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">weightj</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pricej</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">meats</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pricej</span><span style="color: #0000FF;">/</span><span style="color: #000000;">weightj</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pricei</span><span style="color: #0000FF;">/</span><span style="color: #000000;">weighti</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tags</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">by_weighted_value</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">meats</span><span style="color: #0000FF;">)))</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">weight</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">15</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">worth</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tags</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">wi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">price</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">meats</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tags</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">amt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%3.1fkg %s %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">amt</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">amt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">wi</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"(all the)"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"of"</span><span style="color: #0000FF;">),</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">worth</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">amt</span><span style="color: #0000FF;">/</span><span style="color: #000000;">wi</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">price</span>
<span style="color: #000000;">weight</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">amt</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">weight</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
3.0kg (all
3.6kg (all
2.5kg (all
2.4kg (all
3.5kg of welt
Total value: 349.378378
Line 2,584 ⟶ 2,878:
=={{header|PHP}}==
<
$data = [
[
Line 2,648 ⟶ 2,942:
$limit -= $item['weight'];
endforeach;
</syntaxhighlight>
Output:
<pre>Take all the salami
Line 2,655 ⟶ 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,689 ⟶ 3,040:
NIL
(format (sum cadr K) *Scl)
(format (sum caddr K) *Scl) ) )</
Output:
<pre> salami 3.00 95.00
Line 2,699 ⟶ 3,050:
=={{header|PL/I}}==
<
KNAPSACK_CONTINUOUS: Proc Options(main);
/*--------------------------------------------------------------------
Line 2,773 ⟶ 3,124:
item(i).value = value;
End;
End;</
{{out}}
<pre>
Line 2,797 ⟶ 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,863 ⟶ 3,214:
print_results(S, A1, A2, A3, T, TN, W2, V2).
</syntaxhighlight>
Output :
<pre> ?- knapsack.
Line 2,876 ⟶ 3,227:
=={{header|PureBasic}}==
Using the greedy algorithm.
<
name.s
weight.f ;units are kilograms (kg)
Line 2,947 ⟶ 3,298:
Input()
CloseConsole()
EndIf </
Sample output:
<pre>Maximal weight = 15 kg
Line 2,962 ⟶ 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 2,991 ⟶ 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,006 ⟶ 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,049 ⟶ 3,400:
print("Total value of tasty meats:")
print(Total_Value)
}</
'''Sample Input'''
Line 3,070 ⟶ 3,421:
=={{header|Racket}}==
<
(define shop-inventory
'((beef 3.8 36)
Line 3,114 ⟶ 3,465:
(call-with-values (lambda () (continuous-knapsack shop-inventory null 15 0))
report-knapsack)</
{{out}}
Line 3,129 ⟶ 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,172 ⟶ 3,523:
$max-w -= .weight;
last if $last-one;
}</
'''Output:'''
<pre>Item Portion Value
Line 3,185 ⟶ 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,226 ⟶ 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,260 ⟶ 3,611:
===version 2===
<
* 19.09.2014 Walter Pachl translated from FORTRAN
* While this program works with all REXX interpreters,
Line 3,336 ⟶ 3,687:
input.i=name'*'weight'*'value
input.0=i
Return</
{{out}}
<pre># vpu name weight value
Line 3,359 ⟶ 3,710:
=={{header|Ruby}}==
<
[:pork , 5.4, 43],
[:ham , 3.6, 90],
Line 3,378 ⟶ 3,729:
break
end
end</
{{out}}
<pre>
Line 3,392 ⟶ 3,743:
=={{header|Run BASIC}}==
{{incorrect|Run BASIC}}
<
dim wgt(9)
dim price(9)
Line 3,448 ⟶ 3,799:
print "-------- Total ";using("###.#",totTake);chr$(9);"Weight: ";totWgt
end if
next i</
<pre>Best 2 Options
Line 3,459 ⟶ 3,810:
=={{header|Rust}}==
<
let items: [(&str, f32, u8); 9] = [
("beef", 3.8, 36),
Line 3,492 ⟶ 3,843:
}
}
}</
Grab 3.0 kgs of salami
Grab 3.6 kgs of ham
Line 3,502 ⟶ 3,853:
=={{header|SAS}}==
Use LP solver in SAS/OR:
<
data mydata;
input item $ weight value;
Line 3,537 ⟶ 3,888:
print TotalValue;
print {i in ITEMS: WeightSelected[i].sol > 1e-3} WeightSelected;
quit;</
Output:
Line 3,552 ⟶ 3,903:
=={{header|Scala}}==
===Functional approach (Tail recursive)===
<
object ContinousKnapsackForRobber extends App {
Line 3,608 ⟶ 3,959:
println(packer(sortedItems, Lootsack(Nil)))
}</
{{Out}}
<pre>100.00% Salami 3.0 95.00
Line 3,620 ⟶ 3,971:
=={{header|Sidef}}==
{{trans|Perl}}
<
[
[:beef, 3.8, 36],
Line 3,649 ⟶ 4,000:
}
say "#{'-'*28}\ntotal value: #{'%.14g' % value }"</
{{out}}
<pre>
Line 3,663 ⟶ 4,014:
=={{header|Tcl}}==
<
# Uses the trivial greedy algorithm
Line 3,699 ⟶ 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,719 ⟶ 4,070:
lassign $item name mass value
puts [format "\t%.1fkg of %s, value %.2f" $mass $name $value]
}</
Output:
<pre>
Line 3,736 ⟶ 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,762 ⟶ 4,113:
#cast %em
main = solution system items</
output:
<pre><
Line 3,770 ⟶ 4,121:
'salami ': 3.000000e+00,
'welt ': 3.500000e+00></pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="v (vlang)">struct Item {
item string
weight f64
price f64
}
fn main(){
mut left := 15.0
mut items := [
Item{'beef', 3.8, 36},
Item{'pork', 5.4, 43},
Item{'ham', 3.6, 90},
Item{'greaves', 2.4, 45},
Item{'flitch', 4.0, 30},
Item{'brawn', 2.5, 56},
Item{'welt', 3.7, 67},
Item{'salami', 3.0, 95},
Item{'sausage', 5.9, 98}
]
items.sort_with_compare(fn (a &Item, b &Item) int {
if a.weight/a.price < b.weight/b.price {
return -1
} else if a.weight/a.price > b.weight/b.price {
return 1
} else {
return 0
}
})
for item in items {
if item.weight <= left {
println('Take all the $item.item')
if item.weight == left {
return
}
left -= item.weight
} else {
println('Take ${left:.1}kg $item.item')
return
}
}
//println(items)
}</syntaxhighlight>
{{out}}
<pre>
take all the salami
take all the ham
take all the brawn
take all the greaves
take 3.5kg welt
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
{{libheader|Wren-sort}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
import "./math" for Math
import "./sort" for Sort
class Item {
construct new(name, weight, value) {
_name = name
_weight = weight
_value = value
}
name { _name }
weight { _weight }
value { _value }
}
var items = [
Item.new("beef", 3.8, 36),
Item.new("pork", 5.4, 43),
Item.new("ham", 3.6, 90),
Item.new("greaves", 2.4, 45),
Item.new("flitch", 4, 30),
Item.new("brawn", 2.5, 56),
Item.new("welt", 3.7, 67),
Item.new("salami", 3.0, 95),
Item.new("sausage", 5.9, 98)
]
var maxWeight = 15
// sort items by value per unit weight in descending order
var cmp = Fn.new { |i, j| (j.value/j.weight - i.value/i.weight).sign }
Sort.insertion(items, cmp)
System.print("Item Chosen Weight Value Percentage")
System.print("----------- ------ ------ ----------")
var w = maxWeight
var itemCount = 0
var sumValue = 0
for (item in items) {
itemCount = itemCount + 1
if (item.weight <= w) {
sumValue = sumValue + item.value
Fmt.print("$-11s $3.1f $5.2f 100.00", item.name, item.weight, item.value)
} else {
var value = Math.toPlaces(w / item.weight * item.value, 2)
var percentage = Math.toPlaces(w / item.weight * 100, 2)
sumValue = sumValue + value
Fmt.print("$-11s $3.1f $5.2f $6.2f", item.name, w, value, percentage)
break
}
w = w - item.weight
if (w == 0) break
}
System.print("----------- ------ ------")
Fmt.print("$d items 15.0 $6.2f", itemCount, sumValue)</syntaxhighlight>
{{out}}
<pre>
Item Chosen Weight Value Percentage
----------- ------ ------ ----------
salami 3.0 95.00 100.00
ham 3.6 90.00 100.00
brawn 2.5 56.00 100.00
greaves 2.4 45.00 100.00
welt 3.5 63.38 94.59
----------- ------ ------
5 items 15.0 349.38
</pre>
=={{header|XPL0}}==
<
real Weight, Best, ItemWt, TotalWt;
def Items = 9;
Line 3,801 ⟶ 4,277:
Text(0, Name(BestItem)); CrLf(0);
until TotalWt >= 15.0; \all we can steal
]</
Output:
Line 3,814 ⟶ 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,827 ⟶ 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>
|