Knapsack problem/Bounded: Difference between revisions
added Pascal example
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(added Pascal example) |
||
Line 2,857:
</pre>
Takes about 3 seconds on a slow netbook.
=={{header|Pascal}}==
{{works with|FPC}}
Dynamic programming solution (tested with FPC 3.2.2).
<syntaxhighlight lang="pascal">
program KnapsackBounded;
{$mode objfpc}{$j-}
uses
SysUtils, Math;
type
TItem = record
Name: string;
Weight, Value, Count: Integer;
end;
const
NUM_ITEMS = 22;
ITEMS: array[0..NUM_ITEMS-1] of TItem = (
(Name: 'map'; Weight: 9; Value: 150; Count: 1),
(Name: 'compass'; Weight: 13; Value: 35; Count: 1),
(Name: 'water'; Weight: 153; Value: 200; Count: 2),
(Name: 'sandwich'; Weight: 50; Value: 60; Count: 2),
(Name: 'glucose'; Weight: 15; Value: 60; Count: 2),
(Name: 'tin'; Weight: 68; Value: 45; Count: 3),
(Name: 'banana'; Weight: 27; Value: 60; Count: 3),
(Name: 'apple'; Weight: 39; Value: 40; Count: 3),
(Name: 'cheese'; Weight: 23; Value: 30; Count: 1),
(Name: 'beer'; Weight: 52; Value: 10; Count: 3),
(Name: 'suntan cream'; Weight: 11; Value: 70; Count: 1),
(Name: 'camera'; Weight: 32; Value: 30; Count: 1),
(Name: 'T-shirt'; Weight: 24; Value: 15; Count: 2),
(Name: 'trousers'; Weight: 48; Value: 10; Count: 2),
(Name: 'umbrella'; Weight: 73; Value: 40; Count: 1),
(Name: 'waterproof trousers'; Weight: 42; Value: 70; Count: 1),
(Name: 'waterproof overclothes'; Weight: 43; Value: 75; Count: 1),
(Name: 'note-case'; Weight: 22; Value: 80; Count: 1),
(Name: 'sunglasses'; Weight: 7; Value: 20; Count: 1),
(Name: 'towel'; Weight: 18; Value: 12; Count: 2),
(Name: 'socks'; Weight: 4; Value: 50; Count: 1),
(Name: 'book'; Weight: 30; Value: 10; Count: 2)
);
MAX_WEIGHT = 400;
var
D: array of array of Integer; //DP matrix
I, W, V, C, MaxWeight: Integer;
begin
SetLength(D, NUM_ITEMS + 1, MAX_WEIGHT + 1);
for I := 0 to High(ITEMS) do
for W := 0 to MAX_WEIGHT do begin
D[I+1, W] := D[I, W];
for C := 1 to ITEMS[I].Count do begin
if ITEMS[I].Weight * C > W then break;
V := D[I, W - ITEMS[I].Weight * C] + ITEMS[I].Value * C;
if V > D[I+1, W] then
D[I+1, W] := V;
end;
end;
W := MAX_WEIGHT;
MaxWeight := 0;
WriteLn('bagged:');
for I := High(ITEMS) downto 0 do begin
V := D[I+1, W];
C := 0;
while V <> D[I, W] + ITEMS[I].Value * C do begin
Dec(W, ITEMS[I].Weight);
Inc(C);
end;
Inc(MaxWeight, C * ITEMS[I].Weight);
if C <> 0 then
WriteLn(' ', C, ' ', ITEMS[I].Name);
end;
WriteLn('value = ', D[NUM_ITEMS, MAX_WEIGHT]);
WriteLn('weight = ', MaxWeight);
end.
</syntaxhighlight>
{{out}}
<pre>
bagged:
1 socks
1 sunglasses
1 note-case
1 waterproof overclothes
1 suntan cream
1 cheese
3 banana
2 glucose
1 water
1 compass
1 map
value = 1010
weight = 396
</pre>
=={{header|Perl}}==
| |||