Методы решения задачи о рюкзаке
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;
Solve;
Done;
end.
Приложение 3
Реализация полного перебора для задачи о рюкзаке:
program FS;
{$APPTYPE CONSOLE}
uses SysUtils;
type mas = array[1..50] of integer;
Var N, MaxW:integer;{количество предметов, максимальный вес}
W,P,BestP,NowP:mas;
Max:Integer;
procedure Init;
var i:integer;
begin
assign(input,'input.txt');
reset(input);
readln(N, MaxW);
for i:=1 to N do readln(W[i], P[i]);
close(input);
end;
{передаем Nab - номер набранной группы, OstW-вместимость, stoim-цена набранного (еще не набрали нисколько)}
Procedure Search(Nab, OstW:integer; Stoim:integer);
var i:integer;
begin
{здесь OstW-вес который следует набрать из оставшихся. Stoim-стоимость текущего решения}
{Nab - набор предметов. если наполнили рюкзак
и набрали стоимость больше чем имеется, то считаем это новым решением}
if (Nab > N) and (Stoim > Max) then begin {найдено решение}
BestP:=NowP;
Max:=Stoim;
end
{иначе если количество взятых <= обьема. забиваем рюкзак дальше}
else if Nab<=N then {иначе если набрано меньше чем влазит}
for i:=0 to OstW div W[Nab] do begin {идем от 0 до ост. места}
NowP[Nab]:=i; {берем предмет Nab 0..OstW div W[Nab] раз}
Search(Nab+1,OstW-i*W[Nab],Stoim+i*P[Nab]);
{после каждого взятия предмета увеличиваем стоимость набора
и уменьшаем место в рюкзаке на вес предмета, так же увеличиваем
количество раз взятия предмета}
end;
end;
procedure print(name:string; out_:mas; num:integer);
var i:integer;
begin
if num=0 then begin
Writeln('Наилучший набор ', Max);
Writeln;
Write(' Номер предмета:');
for i:=1 to n do write(i: 3);
Writeln;
end else begin
Write(name);
for i:=1 to n do write(out_[i]: 3);
Writeln;
end;
end;
procedure Done;
begin
assign(output,'output.txt');
rewrite(output);
print('Наилучший набор ',bestP,0);
print(' Количество взятых:',BestP,1);
print(' Вес предмета:',W,1);
print('Стоимость предмета:',P,1);
close(output);
end;
begin
init;
Search(1, MaxW, 0);
done;
end.
Приложение 4
Реализация Жадного алгоритма для задачи о рюкзаке:
program Greedy;
{$APPTYPE CONSOLE}
uses SysUtils;
var W, P:array [1..15000] of integer; {веса, цены}
Price:array [1..15000] of real; {относительная ценность}
Take:array [1..15000] of boolean; {использование предметов}
i, N, BestPrice, NowWeight, MaxWeight:integer;
{Количество предметов, Лучшая стоимость, Текущий вес, Макс. вес}
{Считаем что предметы уже отсортированы}
procedure Init;
begin
assign(input,'input.txt');
reset(input);
readln(N, MaxWeight);
for i:=1 to N do readln(W[i], P[i]);
close(input);
end;
procedure Solve;
begin
fillchar(Take, sizeof(Take), False);
i:=0;
while NowWeight+W[i+1]<MaxWeight do begin
inc(i);
BestPrice:= BestPrice + P[i];
NowWeight:= NowWeight + W[i];
Take[i]:= true;
end;
end;
procedure Done;
begin
assign(output,'output.txt');
rewrite(output);
i:=1;
writeln('Максимальная стоимость ',BestPrice);
writeln('Вес предметов максимальной стоимости ',NowWeight);
writeln('Используемые предметы');
writeln('Вес Цена');
while Take[i] do begin
writeln(W[i],' ',P[i]);
inc(i);
end;
close(output);
end;
begin
init;
solve;
done;
end.