57 lines
2.2 KiB
Text
57 lines
2.2 KiB
Text
MODULE KnapsackProblem; (* Knapsack problem: Continuous - based on the Algol W sample, *)
|
|
(* which is based on the EasyLang sample *)
|
|
IMPORT Out;
|
|
|
|
CONST maxItems = 8;
|
|
maxName = 12;
|
|
TYPE ItemDesc = RECORD name : ARRAY maxName OF CHAR;
|
|
weight, cost : REAL
|
|
END;
|
|
Item = POINTER TO ItemDesc;
|
|
|
|
VAR sackItems : ARRAY maxItems + 1 OF Item;
|
|
t : Item;
|
|
weightLeft, w : REAL;
|
|
p, q : INTEGER;
|
|
|
|
PROCEDURE price( a : Item ) : REAL;
|
|
BEGIN
|
|
RETURN a.cost / a.weight
|
|
END price;
|
|
|
|
PROCEDURE newItem( name : ARRAY OF CHAR; weight, cost : REAL ) : Item;
|
|
VAR result : Item;
|
|
BEGIN
|
|
NEW( result );
|
|
result.name := name;
|
|
result.weight := weight;
|
|
result.cost := cost
|
|
RETURN result
|
|
END newItem;
|
|
|
|
BEGIN
|
|
|
|
sackItems[ 0 ] := newItem( "beef", 3.8, 36.0 );sackItems[ 1 ] := newItem( "pork", 5.4, 43.0 );
|
|
sackItems[ 2 ] := newItem( "ham", 3.6, 90.0 );sackItems[ 3 ] := newItem( "greaves", 2.4, 45.0 );
|
|
sackItems[ 4 ] := newItem( "flitch", 4.0, 30.0 );sackItems[ 5 ] := newItem( "brawn", 2.5, 56.0 );
|
|
sackItems[ 6 ] := newItem( "welt", 3.7, 67.0 );sackItems[ 7 ] := newItem( "salami", 3.0, 95.0 );
|
|
sackItems[ 8 ] := newItem( "sausage", 5.9, 98.0 );
|
|
|
|
FOR p := 0 TO maxItems DO
|
|
FOR q := p + 1 TO maxItems DO
|
|
IF price( sackItems[ q ] ) > price( sackItems[ p ] ) THEN
|
|
t := sackItems[ p ];
|
|
sackItems[ p ] := sackItems[ q ];
|
|
sackItems[ q ] := t
|
|
END
|
|
END
|
|
END;
|
|
weightLeft := 15.0;
|
|
p := -1;
|
|
WHILE ( p <= maxItems ) & ( weightLeft > 0.0 ) DO
|
|
INC( p );
|
|
IF sackItems[ p ].weight > weightLeft THEN w := weightLeft ELSE w := sackItems[ p ].weight END;
|
|
Out.Real( w, 12 );Out.String( " kg " );Out.String( sackItems[ p ].name );Out.Ln;
|
|
weightLeft := weightLeft - w
|
|
END
|
|
END KnapsackProblem.
|