Knapsack problem/Bounded: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(added Pascal example) |
||
Line 2,857: | Line 2,857: | ||
</pre> |
</pre> |
||
Takes about 3 seconds on a slow netbook. |
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}}== |
=={{header|Perl}}== |