Knapsack problem/Continuous: Difference between revisions
Content added Content deleted
(→{{header|Vlang}}: Rename "Vlang" in "V (Vlang)") |
(added Pascal example) |
||
Line 2,604: | Line 2,604: | ||
return -sign(vpu - other~vpu)</syntaxhighlight> |
return -sign(vpu - other~vpu)</syntaxhighlight> |
||
Output is the same as for version 1. |
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}}== |
=={{header|Perl}}== |