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

Рассмотрим непрерывную  задачу о ранце, условия для нее  те же самые, отличие лишь в том, что  мы можем взять часть предмета. То есть предметы можно делить. Пусть  у нас есть тот же набор что  и в таб. 1.1, тогда следуя жадному  алгоритму, берем первый и второй предметы, полностью третий предмет  не помещается т.к места осталось всего на 20кг, но мы можем брать  части предметов, тогда возьмем  веса третьего предмета, соответственно и его стоимости, таким образом мы нагрузили рюкзак полностью, стоимость груза стала равна 240у.е. Для непрерывной задачи о рюкзаке жадный алгоритм будет давать оптимальное решение.[7]

{обнуляем список взятых  предметов} 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;

 

2.6 Сравнительный  анализ методов

 

Минусы Полного перебора

Входные данные не велики, для N=7 программа укладывается в 1с. Уже  для N=10 требуется примерно 40с.

Временная сложность O(N!)

Плюсы Полного перебора

Полный перебор дает точное решение.

Простота реализации

Минусы Метода ветвей и  границ

В худшем случае работает как  полный перебор.

Плюсы Метода ветвей и границ

Возможно значительное сокращение времени работы.

Простота реализации.

Минусы Жадного алгоритма

Всегда можно предоставить такой набор, при котором решение  будет не точным.

Плюсы Жадного алгоритма

Высокое время работы, ограниченное только скоростью сортировки, в среднем O(NlogN).

Может работать с большими значениями N.

Не использует дополнительных ресурсов компьютера.

Простота реализации.

Минусы ДП – алгоритма:

Веса предметов целые, если брать вещественные значения, ДП - алгоритм неприменим!

Использование большого количества оперативной памяти для хранения таблиц промежуточных решений.

Для больших значений N количества предметов ДП – алгоритм работает O( ).

Плюсы ДП – алгоритма:

Высокая скорость работы по сравнению с другими алгоритмами (для не больших значений N<50).

Получаем точное решение.

Имеем оптимальные загрузки рюкзака для всех его весов  от 1 до MaxW

На диаграмме 1. показано соотношение времени работы алгоритмов. По вертикальной оси в 1/10000 секунд. По горизонтальной оси в зависимости  от количества предметов. Для ДП алгоритма  для количества n предметов брался вес w=10*n, так как скорость работы ДП алгоритма зависит от произведения w *n.

Диаграмма 1

 

2.7 Модификации  задачи

 

Необходимо вывести только максимальную стоимость, набор нас  не интересует.

В результате работы нужно  получить не только максимальную стоимость, но и сам набор.

На размер рюкзака несколько  ограничений (многомерность задачи).

Каждый предмет можно  брать только лишь один раз.

Предметы можно брать  произвольное количество раз.

Количество раз помещения  предмета в рюкзак фиксировано. Либо для каждого предмета свое, либо для всех предметов одно.

Некоторые предметы должны обязательно быть уложены в рюкзак (имеют приоритет).

Находить несколько оптимальных  решений (одинаковой стоимости, но с  разным содержимым).

 

Заключение

 

В ходе исследования задачи о рюкзаке были выявлены три основных алгоритма решения. Полный перебор, ДП – программирование, жадный алгоритм. Так же был рассмотрен Метод ветвей и границ, но как сокращение полного  перебора. Все методы разделены на две группы. Первая группа – точные методы, сюда входят ДП – алгоритмы, Полный перебор и Метод ветвей и границ. Вторая группа – приближенные методы, к таким методам относится  Жадный алгоритм. Выбор использования  того или иного метода спорный  вопрос, все зависит от постановки задачи, а так же от того, какие  цели поставлены. Если требуется найти  точное решение, то конечно нужно  использовать точные методы, при небольшом  наборе входных данных (предметов  до 10-20), подойдет перебор или метод  ветвей и границ в силу простоты реализации, при больших, следует  использовать ДП – алгоритм. Если же точность решения не так важна, или  входные данные таковы, что ни один из точных методов не работоспособен, остается применять только приближенные алгоритмы. Но остается возможность  комбинирования различных методов  для ускорения, или даже применение каких либо “уловок” для конкретного  примера. Надеяться же на построение полиномиального алгоритма нет  смысла, так как данная задача NP-полна. Безусловно, данная задача очень важна  с точки зрения ее приложения в  реальной жизни. Не смотря на свою “древность”, рюкзак не только не забывается, наоборот, интерес к нему задаче растет. Оптимальная  загрузка транспорта помогает сокращать  расходы, получать большую прибыль. Также задача применяется в криптографии и прикладной математике.

 

Литература

 

Вирт, Н. Алгоритмы и структуры  данных [Текст] / Н. Вирт. – Пер. с англ.-М.Мир, 1989.-360 с., ил.

Визгунов, Н.П. Динамическое программирование в экономических  задачах с применением системы MATLAB [Текст] / Н.П. Визгунов. – Н.Новгород.: ННГУ, 2006. – 48 с.

Кузюрин, Н.Н Сложность  комбинаторных алгоритмов. Курс лекций [Текст] / Н.Н. Кузюрин, С.А.Фомин. – 2005. – 79 с.

Гери, М. Вычислительные машины и труднорешаемые задачи [Текст] / М. Гери, Д. Джонсон. – М.: Мир, 1982 – 416 с.

Окулов, С. М - Программирование в алгоритмах [Текст] / С.М. Окулов. –  М.: БИНОМ. Лаборатория знаний, 2004. – 341 с.: ил.

Окулов, С.М. Информатика  в задачах [Текст] / С.М. Окулов, А.А, Пестов, О.А. Пестов. – Киров: Изд-во ВГПУ, 1998. — 343с.

Царев, В.А. Проектирование, анализ и программная реализация структур данных и алгоритмов: Учебное  пособие [Текст] / В.А. Царев, А.Ф. Дробанов. – Череповец., 2007. – 34 с.

Акулич, И.Л Динамическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов [Текст] / И.Л. Акулич. – М.: Высш. шк., 1986. – 319 с., ил.

Хаггари, Р. Дискретная математика для программистов [Текст] / Р. Хаггари. – М.: Техносфера, 2003. – 320с.

Кормен, Т. Алгоритмы: построение и анализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. — Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с.

 

Приложение 1

 

Автор задачи: С.М. Окулов

В ресторане собираются N посетителей. Посетитель с номером i, имеющий сумму денег Pi и полноту Si, подходит к двери ресторана  во время Ti. Входная дверь ресторана  имеет K состояний открытости. Состояние  открытости двери может изменяться на одну единицу за единицу времени: дверь открывается на единицу  или остается в том же состоянии. В начальный момент времени дверь  закрыта (состояние 0). Посетитель с  номером i входит в ресторан только в том случае, если дверь открыта  специально для него, то есть когда  состояние открытости двери совпадает  с его степенью полноты Si. Если в  момент прихода посетителя состояние двери не совпадает с его степенью полноты, то посетитель уходит и больше не возвращается.

Ресторан работает в течение  времени T.

Требуется, правильно открывая и закрывая дверь, добиться того, чтобы  за время работы ресторана в нем  собрались посетители, общая сумма  денег у которых максимальна.

Решение

Это классическая задача на метод динамического программирования. Состояния открытости двери можно  представить “треугольной решеткой”, изображенной на рисунке. Каждая вершина  определяет степень открытости q в  момент времени t. Некоторым вершинам решетки приписаны веса, равные сумме  денег у посетителя, приходящего  в момент времени t и имеющего степень  полноты, равную q. Требуется найти  путь по решетке, проходящий через вершины, сумма весов которых имеет  максимальное значение. Следует отметить, что нет необходимости хранить  оценки всех вершин. Нам необходимо подсчитать оценки для момента времени t. Это возможно, если известны их значения для всех предыдущих моментов времени, однако для подсчета достаточно помнить  только оценки для момента времени t–1. Приведем более простой пример входных данных:

3 5 6

3 4 1

5 10 1

1 4 1

Соответствующая решетка  приведена на рисунке. Справа на рисунке  указаны моменты времени. Слева  от некоторых вершин решетки приведены  суммы денег у посетителей, приходящих в этот момент времени и имеющих  степень полноты, совпадающей со степенью открытости двери, записанной в вершине решетки. Ответ для  данного примера очевиден: 11.

 

 

Основная процедура, остальные  очевидны:

Procedure Solve;

Var i,j:Integer; {массивы для  формирования оценок вершин решетки}

SOld,SNew:Array[0..MaxK] Of LongInt;

Begin

SOld[0]:=0;

For i:=1 To K Do SOld[i]:=-MaxLongInt;

SNew:=SOld;

For i:=1 To Tend Do Begin{цикл по  моментам времени}

SNew[0]:=SOld[0];

For j:=1 To i Do{цикл по достижимым  состояниям}

SNew[j]:=Max(SOld[j-1],SOld[j]);

{формирование оценок  вершин}

For j:=1 To N Do {цикл по посетителям}

If (T[j]=i) And (SNew[S[j]]<>-MaxLongInt)

{если время прихода  посетителя совпадает

с рассматриваемым моментом времени

и состояние достижимо, то изменяем

оценку вершины, соответствующей  полноте

посетителя}

Then Inc(SNew[S[j]],P[j]);

SOld:=SNew;{запоминаем массив  оценок}

End;

Res:=-MaxLongInt;

For i:=1 To K Do Res:=Max(Res,SNew[i]);

{находим максимальное  значение

в окончательном массиве  оценок}

End;

 

Приложение 2

 

Реализация метода ДП - программирования для задачи о рюкзаке:

program DP2;

{$APPTYPE CONSOLE}

uses SysUtils;

Const MaxW = 200; MaxN = 100;

var Value:array [0..MaxW,0..MaxN] of integer; {массив  значений(сколько можно набрать  для 1..W весов в 1..N предметов)}

Take :array [0..MaxW,0..MaxN] of boolean; {массив  значений брали предмет или  нет}

W,P :array [0..MaxN] of integer; {Массив  весов, массив цен}

i, N, Weight, 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); {обнуляем}

fillchar(Value, sizeof(Value), 0);

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;

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.