Постановка классической задачи о рюкзаке. Основные способы решения задачи комбинаторной оптимизации. Выбор алгоритма решения задач и определение его сложности. Построение математической модели решения задач. Описание процедур и функций программ.
1.1 Способы решения задач 1.2 Выбор алгоритма решения задач и определение его сложностиПусть есть N разных предметов, каждый предмет имеет вес wi и полезность pi , так же имеется максимальный вес W, который можно положить в рюкзак. Задача о загрузке (задача о рюкзаке) и различные ее модификации широко применяются на практике в прикладной математике, криптографии, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д. Рассматриваемая нами задача является NP - полной, то есть для нее не существует полиномиального алгоритма , решающего ее за разумное время, в этом и есть проблема. Вот ее постановка: Имеется набор из N предметов, каждый предмет имеет массу Wi и полезность Vi, i=(1,2..N), требуется собрать набор с максимальной полезностью таким образом, чтобы он имел вес не больше W, где W - вместимость ранца. Считается что NP - полные задачи очень трудноразрешимы, а так же, что если хотя бы для одной из них удастся найти полиномиальный алгоритм, то такой алгоритм будет существовать для любой задачи из этого класса.В ходе выполнения курсовой работы была изучена теория решения задачи о загрузке и разработан алгоритм и его программная реализация, позволяющая пользователю находить решение задачи при любых входных параметрах.var Value:array [0..MAXW,0..MAXN] of integer; {массив значений (сколько можно набрать для 1..W весов в 1..N предметов)} Take :array [0..MAXW,0..
Введение
1. Основная часть
1.1 Способы решения задач
1.2 Выбор алгоритма решения задач и определение его сложности
1.3 Построение математической модели решения задач
2. Расчетная часть
2.1 Расчет тестового примера
2.2 Описание процедур и функций программ
Вывод
В ходе выполнения курсовой работы была изучена теория решения задачи о загрузке и разработан алгоритм и его программная реализация, позволяющая пользователю находить решение задачи при любых входных параметрах. Для разработки программного обеспечения я использовал среду программирования Delphi.
Список литературы
1. Царев, В.А. Проектирование, анализ и программная реализация структур данных и алгоритмов: Учебное пособие [Текст] / В.А. Царев, А.Ф. Дробанов. Череповец., 2009. - 22 с.
2. Визгунов, Н.П. Динамическое программирование в экономических задачах с применением системы MATLAB [Текст] / Н.П. Визгунов. - Н. Новгород.: ННГУ, 2008. - 48 с.
3. Кузюрин, Н.Н Сложность комбинаторных алгоритмов. Курс лекций [Текст] / Н.Н. Кузюрин, С.А.Фомин. - 2005. - 79 с.
4. Окулов, С. М - Программирование в алгоритмах [Текст] / С.М. Окулов. - М.: БИНОМ. Лаборатория знаний, 2004. - 341 с.: ил.
5 .Вентцель Е. С. Элементы динамического программирования. -М.: Наука,1987.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
