89 lines
2.5 KiB
ObjectPascal
89 lines
2.5 KiB
ObjectPascal
program project1;
|
|
uses
|
|
sysutils, classes, math;
|
|
|
|
const
|
|
MaxWeight = 400;
|
|
N = 22;
|
|
|
|
type
|
|
TMaxArray = array[0..N, 0..MaxWeight] of integer;
|
|
|
|
TEquipment = record
|
|
Description : string;
|
|
Weight : integer;
|
|
Value : integer;
|
|
end;
|
|
|
|
TEquipmentList = array[1..N] of TEquipment;
|
|
|
|
var
|
|
M:TMaxArray;
|
|
MaxValue, WeightLeft, i, j : integer;
|
|
S,KnapSack:TStringList;
|
|
L:string;
|
|
List:TEquipmentList;
|
|
|
|
begin
|
|
//Put all the items into an array called List
|
|
L:=
|
|
'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,suntancreme,11,70,camera,32,30,T-shirt,24,15,trousers,48,40,umbrella,73,40,' +
|
|
'waterprooftrousers,42,70,waterproofoverclothes,43,75,notecase,22,80,sunglasses,7,20,towel,18,12,' +
|
|
'socks,4,50,book,30,10';
|
|
S:=TStringList.create;
|
|
S.Commatext:=L;
|
|
|
|
For i:= 1 to N do
|
|
begin
|
|
List[i].Description:=S[3*i - 3];
|
|
List[i].Weight:=strtoint(S[3*i - 2]);
|
|
List[i].Value:=strtoint(S[3*i - 1]);
|
|
end;
|
|
|
|
//create M, a table linking the possible items for each weight
|
|
//and recording the value at that point
|
|
for j := 0 to MaxWeight do
|
|
M[0, j] := 0;
|
|
|
|
for i := 1 to N do
|
|
for j := 0 to MaxWeight do
|
|
if List[i].weight > j then
|
|
M[i, j] := M[i-1, j]
|
|
else
|
|
M[i, j] := max(M[i-1, j], M[i-1, j-List[i].weight] + List[i].value);
|
|
|
|
//get the highest total value by testing every value in table M
|
|
MaxValue := 0;
|
|
for i:=1 to N do
|
|
for j:= 0 to MaxWeight do
|
|
If M[i,j] > MaxValue then
|
|
MaxValue := m[i,j];
|
|
|
|
writeln('Highest total value : ',MaxValue);
|
|
|
|
//Work backwards through the items to find those items that go in the Knapsack (a stringlist)
|
|
KnapSack := TStringList.create;
|
|
WeightLeft := MaxWeight;
|
|
For i:= N downto 1 do
|
|
if M[i,WeightLeft] = MaxValue then
|
|
if M[i-1, WeightLeft - List[i].Weight] = MaxValue - List[i].Value then
|
|
begin
|
|
Knapsack.add(List[i].Description + ' ' + IntToStr(List[i].Weight)+ ' ' + inttostr(List[i].Value));
|
|
MaxValue := MaxValue - List[i].Value;
|
|
WeightLeft := WeightLeft - List[i].Weight;
|
|
end;
|
|
|
|
//Show the items in the knapsack
|
|
writeln('Number of items : ',KnapSack.count);
|
|
writeln('-------------------------');
|
|
For i:= KnapSack.count-1 downto 0 do
|
|
writeln(KnapSack[i]);
|
|
|
|
KnapSack.free;
|
|
S.free;
|
|
writeln('-------------------------');
|
|
writeln('done');
|
|
readln;
|
|
end.
|