(* 
  Given the real-valued objects o1, ..., on (volumes),
  v1, ... ,vn (values), and c (capacity), find the
  binary-valued objects x1, ..., xn (solutions) such that
  v1*x1 + ... + vn*xn is maximized subject to the constraint
  o1*x1 + ... + on*xn <= c.
*)

MODULE knapsack; 
CONST N = 20;
TYPE  RealVector = ARRAY [1..N] OF REAL;
      BinaryVector = ARRAY [1..N] OF [0..1];

PROCEDURE knapsack(Volume,Value: RealVector; 
                   capacity: REAL; VAR Solution: BinaryVector);
VAR i: INTEGER;
    CurrentBest, TotalValue, volume, waste: REAL;
    CurrentSolution: BinaryVector;
BEGIN
  CurrentBest := 0.0;
  TotalValue := 0.0;
  FOR i := 1 TO N DO
    TotalValue := TotalValue + Value[i];
  END;
  volume := 0.0;
  waste := 0.0;
  FORALL
    FOR i := 1 TO N DO
      EITHER
        CurrentSolution[i] := 1;
        volume := volume + Volume[i];
        volume <= capacity
      ORELSE
        CurrentSolution[i] := 0;
        waste := waste + Value[i];
        waste < TotalValue - CurrentBest
      END
    END
  DO
    CurrentBest := TotalValue - waste;
    Solution := CurrentSolution
  END;
END knapsack;

VAR
i: INTEGER;
capacity: REAL;
vols, vals: RealVector;
sol: BinaryVector;
BEGIN
(* initialize problem *)
vols[1] := 20.0;  vols[2] := 5.0;    vols[3] := 6.3;
vols[4] := 1.2;    vols[5] := 83.67;  vols[6] := 0.08;
vols[7] := 3.0E5;  vols[8] := 30.0;  vols[9] := 3.0;
vols[10] := 16.5;  vols[11] := 19.0;  vols[12] := 10.2;
vols[13] := 17.4;  vols[14] := 5.0;  vols[15] := 4.0;
vols[16] := 4.5E2;  vols[17] := 34.0;  vols[18] := 0.43;
vols[19] := 6.5;  vols[20] := 10.3;
vals[1] := 19.0;  vals[2] := 10.2;  vals[3] := 17.4;
vals[4] := 5.0;    vals[5] := 4.0;    vals[6] := 4.5E2;
vals[7] := 34.0;  vals[8] := 0.43;  vals[9] := 6.5;
vals[10] := 10.3;  vals[11] := 20.0;  vals[12] := 5.0;
vals[13] := 6.3;  vals[14] := 1.2;  vals[15] := 83.67;
vals[16] := 0.08;  vals[17] := 3.0E5;  vals[18] := 30.0;
vals[19] := 3.0;  vals[20] := 16.5;
capacity := 50.0;

(* solve problem *)
knapsack(vols, vals, capacity, sol);
FOR i := 1 TO N DO
  WRITE('Item ', i);
  IF sol[i] = 0 THEN
    WRITE(' not');
  END;
  WRITELN(' included (volume=', vols[i], ', value=', vals[i], ')')
END;
END knapsack.

(* The correct output is:
Item 1 not included (volume=20.000000, value=19.000000)
Item 2 not included (volume=5.000000, value=10.200000)
Item 3 included (volume=6.300000, value=17.400000)
Item 4 included (volume=1.200000, value=5.000000)
Item 5 not included (volume=83.670000, value=4.000000)
Item 6 included (volume=0.080000, value=450.000000)
Item 7 not included (volume=300000.000000, value=34.000000)
Item 8 not included (volume=30.000000, value=0.430000)
Item 9 included (volume=3.000000, value=6.500000)
Item 10 not included (volume=16.500000, value=10.300000)
Item 11 not included (volume=19.000000, value=20.000000)
Item 12 not included (volume=10.200000, value=5.000000)
Item 13 not included (volume=17.400000, value=6.300000)
Item 14 not included (volume=5.000000, value=1.200000)
Item 15 included (volume=4.000000, value=83.670000)
Item 16 not included (volume=450.000000, value=0.080000)
Item 17 included (volume=34.000000, value=300000.000000)
Item 18 included (volume=0.430000, value=30.000000)
Item 19 not included (volume=6.500000, value=3.000000)
Item 20 not included (volume=10.300000, value=16.500000)
*)