Knapsack problem/Continuous: Difference between revisions
added Pascal example
(→{{header|Vlang}}: Rename "Vlang" in "V (Vlang)") |
(added Pascal example) |
||
Line 2,604:
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;
TSelItem = record
Name: string;
Weight: Double;
end;
THaul = array of TSelItem;
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;
function Solve(var aItems: array of TItem; aMaxWeight: Double): THaul;
var
I: Integer = 0;
begin
if Length(aItems) = 0 then exit(nil);
TArrayHelper<TItem>.Sort(aItems, TComparer<TItem>.Construct(ItemCmp));
SetLength(Result, Length(aItems));
repeat
Result[I].Name := aItems[I].Name;
Result[I].Weight := Min(aItems[I].Weight, aMaxWeight);
aMaxWeight := aMaxWeight - Result[I].Weight;
Inc(I);
until (aMaxWeight <= 0)or(I = Length(aItems));
SetLength(Result, I);
end;
const
MAX_WEIGHT = Double(15);
var
Items: array of TItem;
I: TSelItem;
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)
];
for I in Solve(Items, MAX_WEIGHT) do
WriteLn(I.Name, #9, FormatFloat('0.0 kg', I.Weight));
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}}==
| |||