106 lines
1.9 KiB
Text
106 lines
1.9 KiB
Text
class
|
|
KNAPSACKZEROONE
|
|
|
|
create
|
|
make
|
|
|
|
feature
|
|
|
|
items: ARRAY [ITEM]
|
|
|
|
max_weight: INTEGER
|
|
|
|
feature
|
|
|
|
make (a_max_weight: INTEGER)
|
|
-- Make an empty knapsack.
|
|
require
|
|
a_max_weight >= 0
|
|
do
|
|
create items.make_empty
|
|
max_weight := a_max_weight
|
|
end
|
|
|
|
add_item (item: ITEM)
|
|
-- Add 'item' to knapsack.
|
|
local
|
|
temp: ITEM
|
|
do
|
|
create temp.make_from_other (item)
|
|
items.force (item, items.count + 1)
|
|
end
|
|
|
|
compute_solution
|
|
local
|
|
M: ARRAY [INTEGER]
|
|
n: INTEGER
|
|
i, j: INTEGER
|
|
w_i, v_i: INTEGER
|
|
item_i: ITEM
|
|
final_items: LINKED_LIST [ITEM]
|
|
do
|
|
n := items.count
|
|
create M.make_filled (0, 1, n * max_weight)
|
|
from
|
|
i := 2
|
|
until
|
|
(i > n)
|
|
loop
|
|
from
|
|
j := 1
|
|
until
|
|
j > max_weight
|
|
loop
|
|
item_i := items [i]
|
|
w_i := item_i.weight
|
|
if w_i <= j then
|
|
v_i := item_i.value
|
|
M [(i - 1) * max_weight + j] := max (M [(i - 2) * max_weight + j], M [(i - 2) * max_weight + j - w_i + 1] + v_i)
|
|
else
|
|
M [(i - 1) * max_weight + j] := M [(i - 2) * max_weight + j]
|
|
end
|
|
j := j + 1
|
|
end
|
|
i := i + 1
|
|
end
|
|
io.put_string ("The final value of the knapsack will be: ")
|
|
io.put_integer (M [(n - 1) * max_weight + max_weight]);
|
|
io.new_line
|
|
--compute the items that fit into the knapsack
|
|
create final_items.make
|
|
io.put_string ("We'll take the following items: %N");
|
|
from
|
|
i := n
|
|
j := max_weight
|
|
until
|
|
i <= 1 or j <= 1
|
|
loop
|
|
item_i := items [i]
|
|
w_i := item_i.weight
|
|
if w_i <= j then
|
|
v_i := item_i.value
|
|
if M [(i - 1) * max_weight + j] = M [(i - 2) * max_weight + j] then
|
|
else
|
|
final_items.extend (item_i)
|
|
io.put_string (item_i.name)
|
|
io.new_line
|
|
j := j - w_i
|
|
end
|
|
else
|
|
end
|
|
i := i - 1
|
|
end
|
|
end
|
|
|
|
feature {NONE}
|
|
|
|
max (a, b: INTEGER): INTEGER
|
|
-- Max of 'a' and 'b'.
|
|
do
|
|
Result := a
|
|
if a < b then
|
|
Result := b
|
|
end
|
|
end
|
|
|
|
end
|