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.