Назначение и технические характеристики программы «Задача о рюкзаке»

Введение

Программа «Задача о рюкзаке» разработана на основании методических указаний по предмету Теория сложности вычислительных процессов.

1. Назначение и область применения

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

2. Технические характеристики

2.1 Постановка задачи

Для некоторого количества видов товаров заданы массы и цены за единицу товара. Необходимо сформировать такой набор товаров, чтобы для заданной массы набора его цена была максимальной.

Для решения задачи был применён метод динамического программирования. Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.

2.2 Описание алгоритма

После ввода исходных данных основной алгоритм программы выполняется следующим образом:

1 Значение оптимального набора m устанавливается равным массе самого лёгкого товара.

2 Вычисляется цена оптимального набора товаров общей массой m путём нахождения максимума из сумм цен товаров, входящих в набор и стоимостей оптимальных наборов товаров общая масса которых меньше m на величину массы конкретного товара:

f(m) = max(f(m - m_i) + p_i),

где m – текущая масса оптимального набора;

m_i – масса i-го товара;

p_i – цена за единицу товара i-го вида.

3 Запоминается товар для которого получен максимум в пункте 2.

4 Значение массы текущего оптимального набора увеличивается на единицу.

5 Если новое значение массы не больше чем заданная масса оптимального набора, то повторить пункты 2 – 4.

6 Если рассчитаны стоимости оптимальных товаров для всех значений массы от массы самого лёгкого товара до заданной массы набора, то начинается формирование оптимального набора.

7 Берётся товар, запомненный в пункте 3 для стоимости набора товаров заданной массы, заносится в список оптимального набора.

8 Масса выбранного товара вычитается из массы оптимального набора.

9 Если масса набора не равна нулю, то берётся товар, запомненный в пункте 3 для стоимости набора товаров  общей массой равной значению, полученному в пункте 8 и заносится в список оптимального набора после чего повторяется пункт 8.

10 Если достигнута нулевая масса, то оптимальный набор сформирован.

2.3 Описание и обоснование выбора способа организации  входных и выходных данных

Входные данные и выходные данные представлены в виде массивов целых чисел, так как это позволяет без труда группировать данные по определённым признакам и получать доступ к конкретным экземплярам данных.