125 lines
5.4 KiB
Text
125 lines
5.4 KiB
Text
BEGIN # Knapsack problem: 0-1 #
|
|
|
|
PR read "bits.incl.a68" PR # include bit manipulation utilities #
|
|
|
|
# returns the next highest integer with the same number of set bits #
|
|
PROC gospers hack = ( INT x )INT: # using Gosper's Hack #
|
|
BEGIN
|
|
INT c = x AND - x;
|
|
INT r = x + c;
|
|
ENTIER ( ENTIER ( ( r XOR x ) / 4 ) / c ) OR r
|
|
END # gospers hack # ;
|
|
|
|
# knapsack items #
|
|
MODE ITEM = STRUCT( STRING name, INT weight, value );
|
|
[]ITEM possible items
|
|
= ( ( "map", 9, 150 ), ( "compass", 13, 35 )
|
|
, ( "water", 153, 200 ), ( "sandwich", 50, 160 )
|
|
, ( "glucose", 15, 60 ), ( "tin", 68, 45 )
|
|
, ( "banana", 27, 60 ), ( "apple", 39, 40 )
|
|
, ( "cheese", 23, 30 ), ( "beer", 52, 10 )
|
|
, ( "suntan cream", 11, 70 ), ( "camera", 32, 30 )
|
|
, ( "t-shirt", 24, 15 ), ( "trousers", 48, 10 )
|
|
, ( "umbrella", 73, 40 ), ( "waterproof trousers", 42, 70 )
|
|
, ( "waterproof overclothes", 43, 75 ), ( "note-case", 22, 80 )
|
|
, ( "sunglasses", 7, 20 ), ( "towel", 18, 12 )
|
|
, ( "socks", 4, 50 ), ( "book", 30, 10 )
|
|
);
|
|
|
|
[ 1 : UPB possible items ]ITEM sack items := possible items;
|
|
|
|
PRIO SWAP = 1;
|
|
OP SWAP = ( REF ITEM a, b )VOID: BEGIN ITEM t = a; a := b; b := t END;
|
|
|
|
# sort the items into descending value order #
|
|
FOR p TO UPB sack items - 1 DO
|
|
FOR q FROM p + 1 TO UPB sack items DO
|
|
IF value OF sack items[ q ] > value OF sack items[ p ] THEN sack items[ p ] SWAP sack items[ q ] FI
|
|
OD
|
|
OD;
|
|
# calculate the maximum value of each number of items, #
|
|
# if they could all be carried #
|
|
[ 1 : UPB possible items ]INT possible value;
|
|
INT curr value := 0;
|
|
FOR p TO UPB sack items - 1 DO
|
|
curr value +:= value OF sack items[ p ];
|
|
possible value[ p ] := curr value
|
|
OD;
|
|
|
|
# sort the items into descending weight order #
|
|
FOR p TO UPB sack items - 1 DO
|
|
FOR q FROM p + 1 TO UPB sack items DO
|
|
IF weight OF sack items[ q ] > weight OF sack items[ p ] THEN sack items[ p ] SWAP sack items[ q ] FI
|
|
OD
|
|
OD;
|
|
|
|
# find the minimum and maximum number of items we can carry #
|
|
# NB - assumes that each item weighs less than the maximum that can #
|
|
# be carried #
|
|
INT max weight = 400;
|
|
INT min carry := 0;
|
|
INT curr weight := weight OF sack items[ 1 ];
|
|
FOR s pos FROM 2 TO UPB sack items WHILE curr weight <= max weight DO
|
|
min carry +:= 1;
|
|
curr weight +:= weight OF sack items[ s pos ]
|
|
OD;
|
|
INT max carry := 0;
|
|
curr weight := weight OF sack items[ UPB sack items ];
|
|
FOR s pos FROM UPB sack items - 1 BY -1 TO 1 WHILE curr weight <= max weight DO
|
|
max carry +:= 1;
|
|
curr weight +:= weight OF sack items[ s pos ]
|
|
OD;
|
|
|
|
INT best items := 0;
|
|
INT best value := 0;
|
|
INT best weight := 0;
|
|
|
|
# for each possible number of items, find the best value for weight #
|
|
# with that many items #
|
|
# we use a bit mask to select the permutations, the maximum #
|
|
# permutation is 2^length - 1 #
|
|
INT max perm = 2 ^ UPB sack items - 1;
|
|
|
|
FOR item count FROM max carry BY -1 TO min carry WHILE best value < possible value[ item count ] DO
|
|
# the lowest permutation is 2^number of items - 1 #
|
|
INT perm := 2 ^ item count - 1;
|
|
|
|
WHILE perm <= max perm DO
|
|
INT v := perm;
|
|
INT weight := 0;
|
|
INT value := 0;
|
|
INT used := 0;
|
|
FOR sack pos TO UPB sack items WHILE v > 0 AND weight <= max weight DO
|
|
IF ODD v THEN
|
|
weight +:= weight OF sack items[ sack pos ];
|
|
value +:= value OF sack items[ sack pos ];
|
|
used +:= 1
|
|
FI;
|
|
v OVERAB 2
|
|
OD;
|
|
IF weight <= max weight AND used = item count THEN
|
|
IF value > best value THEN
|
|
best items := perm;
|
|
best value := value;
|
|
best weight := weight
|
|
FI
|
|
FI;
|
|
perm := gospers hack( perm )
|
|
OD
|
|
OD;
|
|
|
|
print( ( "At least ", whole( min carry, 0 ), " and at most ", whole( max carry, 0 ) ) );
|
|
print( ( " items could be carried", newline ) );
|
|
print( ( "Bast value: ", whole( best value, 0 ), " with weight: ", whole( best weight, 0 ), " is:", newline ) );
|
|
INT items := best items;
|
|
INT count := 0;
|
|
FOR sack pos TO UPB sack items WHILE items > 0 DO
|
|
IF ODD items THEN
|
|
count +:= 1;
|
|
print( ( " ", name OF sack items[ sack pos ], newline ) )
|
|
FI;
|
|
items OVERAB 2
|
|
OD;
|
|
print( ( "total: ", whole( count, 0 ), " items.", newline ) )
|
|
|
|
END
|