Методы решения задачи о рюкзаке (стр. 2 из 4)
Рис 1.1
- 
Рис 1.2
Рис 1.3
Динамическое программирование для задачи о рюкзаке дает точное решение, причем одновременно вычисляются решения для всех размеров рюкзака от 1 до MaxW, но какой ценой? Для хранения таблицы стоимости и запоминания того, брался каждый предмет или нет, требуется порядка O(N*MaxW) памяти, временная сложность равна O(N*MaxW) ;
Опишем основную логику решения: {Загружаем рюкзак если его вместимость = Weight} forWeight:=1 toMaxWdobegin
for i:=1 to N do {берем предметы с 1 по N}
{если вес предмета больше Weight}
{или предыдущий набор лучше выбираемого}
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];
{говорим что вещь i не взята}
Take [Weight, i]:= false;
End
{иначе добавляем к предыдущему набору текущий
предмет}
Else begin
Value [Weight, i]:=Value [Weight - W[i], i-1]
+P[i];
{говорим что вещь i взята}
Take [Weight, i]:= true;
End;
End;
Как было сказано ранее, алгоритм динамического программирования для ‘рюкзака’ дает точное решение путем использования дополнительной памяти O(N*MaxW), временная сложность алгоритма так же будет порядка O(N*MaxW).
2.3 Полный перебор
Название метода говорит само за себя. Чтобы получить решение нужно перебрать все возможные варианты загрузки. Здесь мы будем рассматривать такую постановку задачи. В рюкзак загружаются предметы N различных типов (количество предметов каждого типа не ограничено), каждый предмет типа I имеет вес Wi и стоимость Pi , i=(1,2..N). Требуется определить максимальную стоимость груза вес, которого не превышает W. Очевидна простая рекурсивная реализация данного подхода Рис 1.4. Временная сложность данного алгоритма равна O(N!). Алгоритм имеет сложность факториал и может работать лишь с небольшими значениями N. С ростом N, число вариантов очень быстро растет, и задача становится практически неразрешимой методом полного перебора. На рис 1.5 показано дерево перебора, дерево имеет 4 уровня. В каждом кружочке показан вес предмета, корень дерева – нулевой вес, то есть когда рюкзак пуст. Первый предмет можно выбрать четырьмя способами, второй – тремя, третий – двумя, а дальше можем взять только один оставшийся предмет.
Рис 1.4
Рис 1.5
N - Количество предметов. Пусть MaxW - объем рюкзака, Pi – стоимость i-го предмета, Wi – вес i-го предмета.
{передаем Nab - номер набранной группы, OstW-вместимость, stoim-цена набранного (еще не набрали нисколько)}
Procedure Search(Nab, OstW, 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 пока есть место в ранце}
Search(Nab+1,OstW-i*W[Nab],Stoim+i*P[Nab]);
{после каждого взятия предмета увеличиваем
стоимость набора и уменьшаем место в рюкзаке
на вес предмета, так же увеличиваем количество
раз взятия предмета}
end;
2.4 Метод ветвей и границ
По существу данный метод - это вариация полного перебора, с исключениями заведомо не оптимальных решений. Для полного перебора можно построить дерево решений. Если у нас есть какое то оптимальное решение P, мы пытаемся улучшить его, но если на рассматриваемой в текущий момент ветви решение заведомо хуже чем P то следует остановить поиск и выбрать другую ветвь для рассмотрения. Например, на рис 1.5. есть ограничение на вес рюкзака W=5. Тогда используя метод ветвей и границ можно сократить дерево перебора до такого, рис 1.6. Видно сразу, что количество вариантов для перебора уменьшилось сразу. А именно осталось 8 вариантов исхода, вместо 24 ранее. Но не всегда получается отсеять достаточно много вариантов чтобы скорость работы была заметно увеличена, всегда можно подобрать такие входные данные, для которых метод ветвей и границ даст оценку по времени идентичную полному перебору.
Рис 1.6
2.5 Жадный алгоритм
В случае применения жадного алгоритма поступаем так: сортируем предметы по убыванию стоимости единицы каждого.
, где Pi - относительная стоимость единицы предмета i, Wi- вес предмета i, Vi- стоимость предмета i. Всего N предметов. Пытаемся поместить в рюкзак все что помещается, и одновременно наиболее дорогое по параметру P. Оценим сложность метода. Для сортировки нам потребуется 
плюс проход по N предметам в цикле. Итого 
что в общем случае равно . Скорость работы относительно других алгоритмов высока, но если посмотреть более внимательно, видно, что точное решение мы получим не всегда. Обратим внимание на следующую таблицу Таб1.1. | Номер предмета (i) | Вес предмета (кг) | Цена (У.е) | Относительная цена (У.е/кг) |
| 1 | 10 | 60 | 6 |
| 2 | 20 | 100 | 5 |
| 3 | 30 | 120 | 4 |
Как видно предметы уже отсортированы. Пусть в рюкзак помещается 50кг, следуя алгоритму, берем первый предмет, затем второй, третий предмет уже не помещается. Таким образом, в рюкзаке у нас 30кг стоимостью 160у.е, оставшееся место 20кг. Но если бы мы взяли второй и третий предметы, общий вес поместился в рюкзак, и стоимость его была бы 220у.е. Жадный алгоритм не дает оптимального решения, поэтому он является приближенным алгоритмом.[7] Оказывается качество решения можно улучшить, если сравнить полученный результат с максимальным коэффициентом Vmax ;
. Предполагается, что все предметы не превосходят размера рюкзака, в противном случае их можно просто исключить из рассмотрения.[3]Рассмотрим непрерывную задачу о ранце, условия для нее те же самые, отличие лишь в том, что мы можем взять часть предмета. То есть предметы можно делить. Пусть у нас есть тот же набор что и в таб. 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.