48 lines
1.7 KiB
Plaintext
48 lines
1.7 KiB
Plaintext
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.
|