60 lines
1.5 KiB
ObjectPascal
60 lines
1.5 KiB
ObjectPascal
type
|
|
item = (string, integer, integer);
|
|
|
|
const
|
|
wants: array of item =
|
|
|('map', 9, 150),
|
|
('compass', 13, 35),
|
|
('water', 153, 200),
|
|
('sandwich', 50, 160),
|
|
('glucose', 15, 60),
|
|
('tin', 68, 45),
|
|
('banana', 27, 60),
|
|
('apple', 39, 40),
|
|
('cheese', 23, 30),
|
|
('beer', 52, 10),
|
|
('suntan cream', 11, 70),
|
|
('camera', 32, 30),
|
|
('T-shirt', 24, 15),
|
|
('trousers', 48, 10),
|
|
('umbrella', 73, 40),
|
|
('waterproof trousers', 42, 70),
|
|
('waterproof overclothes', 43, 75),
|
|
('note-case', 22, 80),
|
|
('sunglasses', 7, 20),
|
|
('towel', 18, 12),
|
|
('socks', 4, 50),
|
|
('book', 30, 10)|;
|
|
maxweight = 400;
|
|
|
|
function m(i, w: integer): (List<item>, integer, integer);
|
|
begin
|
|
var chosen := new List<item>;
|
|
if (i < 0) or (w = 0) then
|
|
result := (chosen, 0, 0)
|
|
else if (wants[i].Item2 > w) then
|
|
result := m(i - 1, w)
|
|
else
|
|
begin
|
|
var (l0, w0, v0) := m(i - 1, w);
|
|
var (l1, w1, v1) := m(i - 1, w - wants[i].Item2);
|
|
v1 += wants[i].Item3;
|
|
if (v1 > v0) then
|
|
begin
|
|
l1.Add(wants[i]);
|
|
result := (l1, w1 + wants[i].Item2, v1);
|
|
end
|
|
else result := (l0, w0, v0);
|
|
end;
|
|
end;
|
|
|
|
begin
|
|
var (chosenItems, totalWeight, totalValue) := m(wants.Count - 1, maxweight);
|
|
println('Knapsack Item Chosen Weight Value');
|
|
println('---------------------- ------ -----');
|
|
foreach var it in chosenItems do
|
|
writeln(it.Item1.PadRight(22), it.Item2:7, it.Item3:6);
|
|
println('---------------------- ------ -----');
|
|
writeln('Total ', chosenItems.Count, ' Items Chosen', totalWeight:8, totalValue:6);
|
|
end.
|