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

Цель данной работы – выделить основные методы решения задачи о загрузке, классифицировать и сравнить эти методы. Реализовать алгоритмы решения классической задачи о рюкзаке. Протестировать их и разбить их на две группы: точные и приближенные, сравнить по скорости решения, по точности. Определить в каких случаях следует использовать тот или иной подход к решению задачи. Алгоритмы решения можно разделить на два типа: точные и приближенные. Точные: применение динамического программирования, полный перебор, метод ветвей и границ (сокращение полного перебора). Приближенные алгоритмы: Жадный алгоритм.

Введение
Глава 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