Курсовая работа: Методы решения задачи о рюкзаке

for Weight:=1 to MaxWeight do begin {выбираемоптимумдлявеса Weight}

for i:=1 to N do {берем предметы с 1 по N}

{если вес предмета больше чем текущий вес рюкзака}

{или предыдущий набор дороже выбираемого}

if (W[i]> Weight) or (Value[Weight, i-1] >= Value[Weight-W[i], i-1]+P[i]) then begin

Value[Weight, i]:= Value[Weight, i - 1];

{тогдеаберемпредыдущийнабор}

Take[Weight, i]:= false; {говоримчтовещь i невзята}

end

else begin {иначе добавляем к предыдущему набору текущий предмет}

Value[Weight, i]:= Value[Weight - W[i], i-1] +P[i];

Take[Weight, i]:= true; {говоримчтовещь i взята}

end;

end;

end;

procedure Done;

begin

assign(output,'output.txt');

rewrite(output);

Writeln('Наилучшийнабор ', Value[MaxWeight, N]);

Weight:= MaxWeight;

for i:= N downto 1 do if Take[Weight, i] then begin

Write(i,' ');

Weight:= Weight-W[i];

end;

close(output);

end;

begin

Init;