83 lines
2.2 KiB
Plaintext
83 lines
2.2 KiB
Plaintext
class
|
|
KNAPSACK
|
|
|
|
create
|
|
make
|
|
|
|
feature
|
|
|
|
make
|
|
do
|
|
create panacea;
|
|
panacea := [3000, 0.3, 0.025]
|
|
create ichor;
|
|
ichor := [1800, 0.2, 0.015]
|
|
create gold;
|
|
gold := [2500, 2.0, 0.002]
|
|
create sack;
|
|
sack := [0, 25.0, 0.25]
|
|
find_solution
|
|
end
|
|
|
|
feature {NONE}
|
|
|
|
panacea: TUPLE [value: INTEGER; weight: REAL_64; volume: REAL_64]
|
|
|
|
ichor: TUPLE [value: INTEGER; weight: REAL_64; volume: REAL_64]
|
|
|
|
gold: TUPLE [value: INTEGER; weight: REAL_64; volume: REAL_64]
|
|
|
|
sack: TUPLE [value: INTEGER; weight: REAL_64; volume: REAL_64]
|
|
|
|
find_solution
|
|
-- Solution for unbounded Knapsack Problem.
|
|
local
|
|
totalweight, totalvolume: REAL_64
|
|
maxpanacea, maxichor, maxvalue, maxgold: INTEGER
|
|
n: ARRAY [INTEGER]
|
|
r: TUPLE [value: INTEGER; weight: REAL_64; volume: REAL_64]
|
|
do
|
|
maxpanacea := minimum (sack.weight / panacea.weight, sack.volume / panacea.volume).rounded
|
|
maxichor := minimum (sack.weight / ichor.weight, sack.volume / ichor.volume).rounded
|
|
maxgold := minimum (sack.weight / gold.weight, sack.volume / gold.volume).rounded
|
|
create n.make_filled (0, 1, 3)
|
|
create r
|
|
across
|
|
0 |..| maxpanacea as p
|
|
loop
|
|
across
|
|
0 |..| maxichor as i
|
|
loop
|
|
across
|
|
0 |..| maxgold as g
|
|
loop
|
|
r.value := g.item * gold.value + i.item * ichor.value + p.item * panacea.value
|
|
r.weight := g.item * gold.weight + i.item * ichor.weight + p.item * panacea.weight
|
|
r.volume := g.item * gold.volume + i.item * ichor.volume + p.item * panacea.volume
|
|
if r.value > maxvalue and r.weight <= sack.weight and r.volume <= sack.volume then
|
|
maxvalue := r.value
|
|
totalweight := r.weight
|
|
totalvolume := r.volume
|
|
n [1] := p.item
|
|
n [2] := i.item
|
|
n [3] := g.item
|
|
end
|
|
end
|
|
end
|
|
end
|
|
io.put_string ("Maximum value achievable is " + maxValue.out + ".%N")
|
|
io.put_string ("This is achieved by carrying " + n [1].out + " panacea, " + n [2].out + " ichor and " + n [3].out + " gold.%N")
|
|
io.put_string ("The weight is " + totalweight.out + " and the volume is " + totalvolume.truncated_to_real.out + ".")
|
|
end
|
|
|
|
minimum (a, b: REAL_64): REAL_64
|
|
-- Smaller of 'a' and 'b'.
|
|
do
|
|
Result := a
|
|
if a > b then
|
|
Result := b
|
|
end
|
|
end
|
|
|
|
end
|