Министерство образования и науки Российской Федерации. Государственное образовательное учреждение высшего профессионального образования «Вятский государственный гуманитарный университет»

ФАКУЛЬТЕТ ИНФОРМАТИКИ

Кафедра прикладной математики и информатики

КУРСОВАЯ РАБОТА

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

Выполнил студент 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.  Некоторые вещи имею больший приоритет, чем другие

Цель данной работы – выделить основные методы решения задачи о загрузке, классифицировать и сравнить эти методы.

Реализовать алгоритмы решения классической задачи о рюкзаке. Протестировать их и разбить их на две группы: точные и приближенные, сравнить по скорости решения, по точности. Определить в каких случаях следует использовать тот или иной подход к решению задачи.

Алгоритмы решения можно разделить на два типа: точные и приближенные. Точные: применение динамического программирования, полный перебор, метод ветвей и границ (сокращение полного перебора). ............