MODULE Knapsack EXPORTS Main;

FROM IO IMPORT Put;
FROM Fmt IMPORT Int, Real;

TYPE Bounty = RECORD
  value: INTEGER;
  weight, volume: REAL;
END;

VAR totalWeight, totalVolume: REAL;
    maxPanacea, maxIchor, maxGold, maxValue: INTEGER := 0;
    n: ARRAY [1..3] OF INTEGER;
    panacea, ichor, gold, sack, current: Bounty;

BEGIN
  panacea := Bounty{3000, 0.3, 0.025};
  ichor   := Bounty{1800, 0.2, 0.015};
  gold    := Bounty{2500, 2.0, 0.002};
  sack    := Bounty{0, 25.0, 0.25};

  maxPanacea := FLOOR(MIN(sack.weight / panacea.weight, sack.volume / panacea.volume));
  maxIchor := FLOOR(MIN(sack.weight / ichor.weight, sack.volume / ichor.volume));
  maxGold := FLOOR(MIN(sack.weight / gold.weight, sack.volume / gold.volume));

  FOR i := 0 TO maxPanacea DO
    FOR j := 0 TO maxIchor DO
      FOR k := 0 TO maxGold DO
        current.value := k * gold.value + j * ichor.value + i * panacea.value;
        current.weight := FLOAT(k) * gold.weight + FLOAT(j) * ichor.weight + FLOAT(i) * panacea.weight;
        current.volume := FLOAT(k) * gold.volume + FLOAT(j) * ichor.volume + FLOAT(i) * panacea.volume;
        IF current.weight > sack.weight OR current.volume > sack.volume THEN
          EXIT;
        END;
        IF current.value > maxValue THEN
          maxValue := current.value;
          totalWeight := current.weight;
          totalVolume := current.volume;
          n[1] := i; n[2] := j; n[3] := k;
        END;
      END;
    END;
  END;
  Put("Maximum value achievable is " & Int(maxValue) & "\n");
  Put("This is achieved by carrying " & Int(n[1]) & " panacea, " & Int(n[2]) & " ichor and " & Int(n[3]) & " gold items\n");
  Put("The weight of this carry is " & Real(totalWeight) & " and the volume used is " & Real(totalVolume) & "\n");
END Knapsack.