73 lines
2.7 KiB
ObjectPascal
73 lines
2.7 KiB
ObjectPascal
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.
|