Министерство образования и науки Российской Федерации. Государственноеобразовательное учреждение высшего профессионального образования «Вятскийгосударственный гуманитарный университет»
ФАКУЛЬТЕТ ИНФОРМАТИКИ
Кафедра прикладной математики и информатики
КУРСОВАЯ РАБОТА
Методы решения задачи о рюкзаке
Выполнилстудент 3 курса группы ПМ-31
ПеревощиковСергей Владимирович
Научныйруководитель: к.п.н, доцент кафедры
прикладнойматематики и информатики
Разова ЕленаВладимировна
Киров 2010
/>Оглавление
Введение
Глава 1 Задача о загрузке,рюкзаке, ранце. Постановка и NP-полнотазадачи
1.1 Постановка задачи о рюкзаке
1.2 NP – полнота задачи
Глава 2 Методы решения задачи орюкзаке
2.1 Классификация методов
2.2 Динамическое программирование
2.3 Полный перебор
2.4 Метод ветвей и границ
2.5 Жадный алгоритм
2.6 Сравнительный анализ методов
2.7 Модификации задачи
Заключение
Литература
Приложение 1
Приложение 2
Приложение 3
Приложение 4
Введение
Классическая задача орюкзаке (о загрузке) известна очень давно, ниже приведена ее формализация.Пусть есть N разных предметов, каждый предметимеет вес wi и полезность pi, так же имеется максимальный вес W, который можно положить в рюкзак.Требуется собрать такой набор предметов P, чтобы полезность их была наибольшей, а суммарный вес непревышал W.[6]. Конечно, никто не собираетсяписать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в походили в путешествие, тут все слишком просто, и никто не задумывается об этом, носуществует и более широкое применение.
Задача о загрузке(задача о рюкзаке) и различные её модификации широко применяются на практике вприкладной математике, криптографии, экономике, логистике, для нахождениярешения оптимальной загрузки различных транспортных средств: самолетов,кораблей, железнодорожных вагонов и т.д.
Рассматриваемая намизадача является NP – полной, тоесть для нее не существует полиномиального алгоритма, решающего её за разумноевремя, в этом и есть проблема. Либо мы выбираем быстрый алгоритм, но он какизвестно не всегда решает задачу наилучшим образом, либо выбираем точный,который опять же не является работоспособным для больших значений. Существуетнесколько модификаций задачи.
1. Каждый предмет можно брать толькоодин раз.
2. Каждый предмет можно брать сколькоугодно раз.
3. Каждый предмет можно братьопределенное количество раз
4. На размер рюкзака имеется несколькоограничений.
5. Некоторые вещи имею большийприоритет, чем другие
Цель данной работы –выделить основные методы решения задачи о загрузке, классифицировать и сравнитьэти методы.
Реализовать алгоритмырешения классической задачи о рюкзаке. Протестировать их и разбить их на двегруппы: точные и приближенные, сравнить по скорости решения, по точности.Определить в каких случаях следует использовать тот или иной подход к решениюзадачи.
Алгоритмы решенияможно разделить на два типа: точные и приближенные. Точные: применениединамического программирования, полный перебор, метод ветвей и границ(сокращение полного перебора). Приближенные алгоритмы: Жадный алгоритм.
/>Глава 1Задача о загрузке, рюкзаке, ранце. Постановка и NP-полнота задачи
/>1.1 Постановка задачи о рюкзаке
Задача о ранце – однаиз задач комбинаторной оптимизации. Классическая задача о ранце известна оченьдавно. Вот её постановка: Имеется набор из N предметов, каждый предмет имеет массу Wi и полезность Vi, i=(1,2..N),требуется собрать набор с максимальной полезностью таким образом, чтобы он имелвес не больше W, где W – вместимость ранца. Традиционно полагают что Wi, Vi, W, P – целыенеотрицательные числа, но встречаются и другие постановки, условия в которыхмогут отличаться.[6] Возможны следующие вариации задачи:
Каждый предмет можнобрать только один раз. Формализуем. Пусть задано конечное множество предметов />, для каждого />, определена стоимость pi и вес wi, тогда нужно максимизировать /> , при ограничениях />, где W-вместимостьранца, а xi=1, если предмет взят для загрузки и xi=0 если не взят. Если на размеррюкзака имеется только одно ограничение, то задача называется одномерной, впротивном случае – многомерной.
Каждый предмет можнобрать m раз. Формализация аналогична,разница лишь в том, что xi принимает значения на интервале (0..m).
Каждый предмет можнобрать неограниченное количество раз. Очевидно, что xi лежит в диапазоне (0..[W/wi]) квадратные скобочки означают целуючасть числа. [6]
Если же значения весови цен предметов не целые числа, такая задача будет называться непрерывнойзадачей о рюкзаке, если же числа целые, то соответственно дискретной. Например,если мы имеем дело с золотыми слитками, мы не можем их делить – это дискретнаязадача, а если с золотым песком, то это непрерывная задача о рюкзаке./>1.2 NP – полнота задачи
Большинствоиспользуемых алгоритмов имеют полиномиальное время работы, если размер входныхданных – n, то время их работы в худшем случаеоценивается как /> где k этоконстанта. Но встречаются задачи, которые нельзя разрешить за полиномиальноевремя. Это класс NP — полных задач.Некоторые задачи этого класса на первый взгляд аналогичны задачам разрешимым заполиномиальное время, но это далеко не так. Задача называется NP — полной, еслидля нее не существует полиномиального алгоритма.[3] Алгоритм называетсяполиномиальным, если его сложность O(N) в худшем случае ограничена сверхунекоторым многочленом (полиномом) от N. Такие задачи возникают очень часто в различных областях: в булевойлогике, в теории графов, теории множеств, кодировании информации, в алгебре, вбиологии, физике, экономике, теории автоматов и языков. Считается что NP — полные задачи оченьтрудноразрешимы, а так же, что если хотя бы для одной из них удастся найтиполиномиальный алгоритм, то такой алгоритм будет существовать для любой задачииз этого класса. Над поиском полиномиальных алгоритмов к таким задачамтрудились многие ученые, и все же и все же при таком разнообразии NP — полных задач, ни для одной из нихдо сих пор не найдено полиномиального алгоритма.[10]. Из всего вышесказанногоследует, что если известна NP — полнота задачи, то лучше потратить время на построение приближенного алгоритма,чем пытаться построить полиномиальный, или же, если это позволяют условия, использоватьалгоритмы с экспоненциальной сложностью работы
/>Глава 2Методы решения задачио рюкзаке
/>2.1 Классификация методов
На практике оченьчасто возникают NP-полные задачи,задач о рюкзаке – одна из них. Конечно надежд, на то что для них найдетсяполиномиальный алгоритм практически нет, но из этого не следует что с задачейнельзя ничего сделать. Во первых, очень часто удается построить полиномиальныйалгоритм для NP – полной задачи, конечно он дастприближенное, а не точное решение, но зато будет работать за реальное время. Вовторых, данные могут быть таковы, что экспоненциальный алгоритм, напримерпереборный сможет работать на них разумное время. К точным методам относятся:Полный перебор, метод ветвей и границ, ДП – программирование. К приближенным:Жадные алгоритмы. Полный перебор – перебор всех вариантов (всех состояний)–малоэффективный, но точный метод. Метод ветвей и границ – по сути сокращениеполного перебора с отсечением заведомо “плохих” решений. ДП – алгоритм,основанный на принципе оптимальности Беллмана. Жадный алгоритм – основан нанахождении относительно хорошего и “дешевого” решения.
/>2.2 Динамическое программирование
В основе методадинамического программирования лежит принцип оптимальности Беллмана:”Каково быни было состояние системы перед очередным шагом, надо выбирать управление наэтом шаге так, чтобы выигрыш на этом шаге плюс оптимальный выигрыш на всех последующихшагах был оптимальным”. Проще говоря оптимальное решение на i шаге находится исходя из найденныхранее оптимальных решений на предшествующих шагах. Из этого следует, что длятого чтобы найти оптимальное решение на последнем шаге надо сначала найтиоптимальное решения для первого, затем для второго и так далее пока не пройдемвсе шаги до последнего.
Имеется набор из N предметов. Пусть MaxW — объем рюкзака, Pi – стоимость i-го предмета, Wi – вес i-го предмета. Value [W, i] – максимальнаясумма, которую надо найти. Суть метода динамического программирования – накаждом шаге по весу 1меньше W проверим стоит ли его брать.
Если его взять то весстанет W-Wi, тогда Value[W, i] = Value[W – Wi, i-1] + Pi (для Value[W – Wi, i-1]) решение уже найдено остаетсятолько прибавить Pi.
Если его не брать товес останется тем же и Value[W, i] = Value[W – Wi, i-1]. =Из двух вариантоввыбирается тот, который дает наибольший результат. Рассмотрим алгоритмподробнее.
/>
Рис 1.1
-/>
Рис 1.2
/>
Рис 1.3
Динамическоепрограммирование для задачи о рюкзаке дает точное решение, причем одновременновычисляются решения для всех размеров рюкзака от 1 до MaxW, но какой ценой? Для хранения таблицы стоимости изапоминания того, брался каждый предмет или нет, требуется порядка O(N*MaxW) памяти,временная сложность равна O(N*MaxW) ;
Опишем основную логикурешения: {Загружаем рюкзак если его вместимость = Weight} for Weight:=1 to MaxW dobegin
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
{иначе добавляем кпредыдущему набору текущий
предмет}
Elsebegin
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 Nabthen
{иначе если набраноменьше чем влазит}
for i:=0 to OstW divW[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.62.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] 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
· Получаем точноерешение.
· Имеем оптимальныезагрузки рюкзака для всех его весов от 1 до MaxW
На диаграмме 1.показано соотношение времени работы алгоритмов. По вертикальной оси в 1/10000секунд. По горизонтальной оси в зависимости от количества предметов. Для ДПалгоритма для количества nпредметов брался вес w=10*n, так как скорость работы ДПалгоритма зависит от произведения w *n.
/>
Диаграмма 1
2.7 Модификации задачи
1. Необходимовывести только максимальную стоимость, набор нас не интересует.
2. В результатеработы нужно получить не только максимальную стоимость, но и сам набор.
3. На размер рюкзаканесколько ограничений (многомерность задачи).
4. Каждый предметможно брать только лишь один раз.
5. Предметы можнобрать произвольное количество раз.
6. Количество разпомещения предмета в рюкзак фиксировано. Либо для каждого предмета свое, либодля всех предметов одно.
7. Некоторыепредметы должны обязательно быть уложены в рюкзак (имеют приоритет).
8. Находитьнесколько оптимальных решений (одинаковой стоимости, но с разным содержимым).
Заключение
В ходеисследования задачи о рюкзаке были выявлены три основных алгоритма решения.Полный перебор, ДП – программирование, жадный алгоритм. Так же был рассмотренМетод ветвей и границ, но как сокращение полного перебора. Все методы разделенына две группы. Первая группа – точные методы, сюда входят ДП – алгоритмы,Полный перебор и Метод ветвей и границ. Вторая группа – приближенные методы, ктаким методам относится Жадный алгоритм. Выбор использования того или иногометода спорный вопрос, все зависит от постановки задачи, а так же от того,какие цели поставлены. Если требуется найти точное решение, то конечно нужноиспользовать точные методы, при небольшом наборе входных данных (предметов до10-20), подойдет перебор или метод ветвей и границ в силу простоты реализации,при больших, следует использовать ДП – алгоритм. Если же точность решения нетак важна, или входные данные таковы, что ни один из точных методов неработоспособен, остается применять только приближенные алгоритмы. Но остаетсявозможность комбинирования различных методов для ускорения, или даже применениекаких либо “уловок” для конкретного примера. Надеяться же на построениеполиномиального алгоритма нет смысла, так как данная задача NP-полна. Безусловно, данная задачаочень важна с точки зрения ее приложения в реальной жизни. Не смотря на свою“древность”, рюкзак не только не забывается, наоборот, интерес к нему задачерастет. Оптимальная загрузка транспорта помогает сокращать расходы, получатьбольшую прибыль. Также задача применяется в криптографии и прикладнойматематике.
/>Литература
1. Вирт, Н.Алгоритмы и структуры данных [Текст] / Н. Вирт. – Пер. с англ.-М.Мир, 1989.-360с., ил.
2. Визгунов, Н.П. Динамическоепрограммирование в экономических задачах с применением системы MATLAB [Текст] /Н.П. Визгунов. – Н.Новгород.: ННГУ, 2006. – 48 с.
3. Кузюрин, Н.НСложность комбинаторных алгоритмов. Курс лекций [Текст] / Н.Н. Кузюрин,С.А.Фомин. – 2005. – 79 с.
4. Гери, М.Вычислительные машины и труднорешаемые задачи [Текст] / М. Гери, Д. Джонсон. –М.: Мир, 1982 – 416 с.
5. Окулов, С. М — Программирование в алгоритмах [Текст] / С.М. Окулов. – М.: БИНОМ. Лабораториязнаний, 2004. – 341 с.: ил.
6. Окулов, С.М. Информатика в задачах[Текст] / С.М. Окулов, А.А, Пестов, О.А. Пестов. – Киров: Изд-во ВГПУ, 1998. —343с.
7. Царев, В.А. Проектирование,анализ и программная реализация структур данных и алгоритмов: Учебное пособие [Текст]/ В.А. Царев, А.Ф. Дробанов. – Череповец., 2007. – 169 с.
8. Акулич, И.ЛДинамическое программирование в примерах и задачах: Учеб. пособие для студентовэконом. спец. вузов [Текст] / И.Л. Акулич. – М.: Высш. шк., 1986. – 319 с., ил.
9. Хаггари, Р. Дискретнаяматематика для программистов [Текст] / Р. Хаггари. – М.: Техносфера, 2003. –320с.
10. Кормен, Т. Алгоритмы: построение ианализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. — Под ред. И. В.Красикова. — 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 ToK Do SOld[i]:=-MaxLongInt;
SNew:=SOld;
For i:=1 ToTend Do Begin{цикл по моментам времени}
SNew[0]:=SOld[0];
For j:=1 Toi 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 ToK Do Res:=Max(Res,SNew[i]);
{находим максимальноезначение
в окончательноммассиве оценок}
End;
Приложение 2
Реализация метода ДП — программирования для задачи о рюкзаке:
programDP2;
{$APPTYPECONSOLE}
usesSysUtils;
Const MaxW= 200; MaxN = 100;
varValue: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;
procedureInit;
begin
assign(input,'input.txt');
reset(input);
readln(N,MaxWeight);
for i:=1 toN do readln(W[i], P[i]);
close(input);
end;
procedureSolve;
begin
fillchar(Take,sizeof(Take), false); {обнуляем}
fillchar(Value,sizeof(Value), 0);
forWeight:=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;
procedureDone;
begin
assign(output,'output.txt');
rewrite(output);
Writeln('Наилучший набор ', Value[MaxWeight, N]);
Weight:=MaxWeight;
for i:= Ndownto 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;
{$APPTYPECONSOLE}
uses SysUtils;
type mas =array[1..50] of integer;
Var N,MaxW:integer;{количество предметов, максимальный вес}
W,P,BestP,NowP:mas;
Max:Integer;
procedureInit;
vari:integer;
begin
assign(input,'input.txt');
reset(input);
readln(N,MaxW);
for i:=1 toN do readln(W[i], P[i]);
close(input);
end;
{передаем Nab — номернабранной группы, OstW-вместимость, stoim-цена набранного (еще не набралинисколько)}
ProcedureSearch(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
for i:=0 toOstW 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;
procedureprint(name:string; out_:mas; num:integer);
vari:integer;
begin
if num=0then begin
Writeln('Наилучшийнабор ', Max);
Writeln;
Write(' Номерпредмета:');
for i:=1 ton do write(i: 3);
Writeln;
end elsebegin
Write(name);
for i:=1 ton do write(out_[i]: 3);
Writeln;
end;
end;
procedureDone;
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
Реализация Жадногоалгоритма для задачи о рюкзаке:
programGreedy;
{$APPTYPECONSOLE}
usesSysUtils;
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;
{Количество предметов,Лучшая стоимость, Текущий вес, Макс. вес}
{Считаем что предметыуже отсортированы}
procedureInit;
begin
assign(input,'input.txt');
reset(input);
readln(N,MaxWeight);
for i:=1 toN do readln(W[i], P[i]);
close(input);
end;
procedureSolve;
begin
fillchar(Take,sizeof(Take), False);
i:=0;
whileNowWeight+W[i+1]
inc(i);
BestPrice:=BestPrice + P[i];
NowWeight:=NowWeight + W[i];
Take[i]:=true;
end;
end;
procedureDone;
begin
assign(output,'output.txt');
rewrite(output);
i:=1;
writeln('Максимальнаястоимость ',BestPrice);
writeln('Вес предметов максимальнойстоимости ',NowWeight);
writeln('Используемые предметы');
writeln('Вес Цена');
whileTake[i] do begin
writeln(W[i],'',P[i]);
inc(i);
end;
close(output);
end;
begin
init;
solve;
done;
end.