program project1;
uses
  sysutils, classes, math;

const
  MaxWeight = 400;
  N = 21;

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, Sum : 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 ,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
   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.