Сравнительный анализ алгоритмов решения задачи о рюкзаке
Введение
Классическая задача о рюкзаке (задача о ранце, о загрузке) известна очень давно. В общем виде задача формулируется следующим образом. Имеется N предметов массой wi и ценностью pi. Также имеется максимальный вес W. Требуется собрать рюкзак с максимальной ценностью предметов внутри, суммарный вес которых не должен превышать W.Задача о рюкзаке применяется в различных областях знаний: в математике, информатике, в криптографии. В одной из работ по вычислительной лингвистике предложена формулировка задачи автоматического реферирования текстов. На основе задачи о ранце был создан первый алгоритм асимметричного шифрования. Также задача о рюкзаке может служить моделью для большого числа промышленных задач: размещение грузов на складе минимальной площади, раскройка ткани – из имеющегося куска материала получить максимальное число выкроек определённой формы, расчет оптимальных капиталовложений.
Содержание
Введение
Задача о рюкзаке. Методы решения
1Постановка задачи о рюкзаке и классификация методов
2Точные методы решения
2.1Полный перебор
2.2Метод ветвей и границ
2.3Перебор с возвратом
2.4Динамическое программирование
3Приближенные алгоритмы
3.1Жадный алгоритм
3.2Генетический алгоритм
Выводы по разделу
Сравнительный анализ алгоритмов
1Выбор языка и среды программирования
2Реализация алгоритмов
2.1Полный перебор
2.2Перебор с возвратом
2.3Метод ветвей и границ
2.4Динамическое программирование
2.5Жадный алгоритм
3Сравнение алгоритмов
Выводы по разделу
Заключение
Библиографический список
Приложения
список
Додонова, М. М. ИЗУЧЕНИЕ РАЗЛИЧНЫХ ПОСТАНОВОК ЗАДАЧИ О РЮКЗАКЕ И МЕТОДОВ ИХ РЕШЕНИЯ // Молодежь и наука: сборник материалов Х Юбилейной Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых с международным участием, посвященной 80-летию образования Красноярского края [Электронный ресурс]. — Красноярск: Сибирский федеральный ун-т, 2014. URL: https://elib.sfu-kras.ru/handle/2311/19290.
Задача о рюкзаке [Электронный ресурс]. URL: https://ru.wikipedia.org/wikiУравнение Беллмана [Электронный ресурс]. URL: https://ru.wikipedia.org/wikiКоролёва А.С., Юровская М.Б. Генетический алгоритм решения задачи о ранце // Студенческая наука XXI века : материалы VI Междунар. студенч. науч.–практ. конф. – Чебоксары: ЦНС «Интерактив плюс», 2015. – С 83 – 84.
Microsoft Visual Studio [Электронный ресурс]. URL: https://ru.wikipedia.org/wiki/Microsoft_Visual_Studio
Данный метод – это вариация полного перебора с исключением заведомо плохих решений. Для этого нужно отсортировать предметы по их удельной стоимости и строить дерево полного перебора. Его улучшение заключается в том, что в процессе построения дерева для каждого узла оценивается верхняя граница ценности решения, и продолжается построение дерева только для узла с максимальной оценкой. Когда максимальная верхняя граница оказывается в листе дерева, алгоритм заканчивает свою работу [2]. Временная сложность метода ветвей и границ совпадает с временной сложностью алгоритма полного перебора и равна O(2^n).