Knapsack problem/Continuous: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(→{{header|Vlang}}: Rename "Vlang" in "V (Vlang)") |
m (→{{header|Wren}}: Minor tidy) |
||
| (4 intermediate revisions by 2 users not shown) | |||
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}}==
Line 2,604 ⟶ 2,725:
return -sign(vpu - other~vpu)</syntaxhighlight>
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}}==
Line 3,993 ⟶ 4,179:
{{libheader|Wren-math}}
{{libheader|Wren-sort}}
<syntaxhighlight lang="
import "./math" for Math
import "./sort" for Sort
class Item {
| |||