Xreferat.com » Рефераты по информатике и программированию » Методы решения задачи о рюкзаке

Методы решения задачи о рюкзаке

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

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.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: