Решение задачи о рюкзаке

В предыдущих лекциях была приведенаупрощенная задача о рюкзаке. Здесь эта задача будет сформулирована в классическомвиде и решена с помощью рекурсивного алгоритма.

Классическая формулировка задачидопускает выбор одинаковых предметовпри размещении их в рюкзаке. Математическая модель классической задачи о рюкзаке выглядит следующим образом:

где – неизвестные (количество предметов каждого типа), которые требуется найти; –объемыпредметов; –стоимость единицы объема каждогопредмета; –вместимость рюкзака;.

Решением задачи при такой постановке будет вектор Каждыйэлемент вектора может принимать целоезначение из отрезка При этом, если то -й предмет не выбран,иесли то -хпредметов в рюкзак помещено единиц.

Обозначим – отрезок векторарешения Аналогичным образом введем отрезок стоимостей. Тогда максимальная стоимость рюкзака может быть записана в векторной форме:

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

, ,

, ,

,

, …, , .

Схема решения задачи о рюкзаке с помощью рекурсивного алгоритма при , изображена на рис. 4.

Рис. 4.Схема рекурсивного решения задачи коммивояжера

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

Вершины соединены дугами, указывающими связь между этапами решения. Каждая дуга имеет метку, обозначающую предположение, прикоторомрешаетсяочередной этап.

Для примера, рассмотрим маршрут, образованный дугами с метками и

Первый этапв этом маршруте отмечен меткой означающей, что приразмещении в рюкзакедвухпредметов с номером 3 стоимость рюкзака станет единиц, и при этом в рюкзаке останется единиц объема.

Второй этап имеет метку . Решение на этом этапе осуществляется в предположении, что в рюкзаке два предмета с номером 3 и один предмет с номером 2. Поэтому и .

Натретьемэтапе завершаетсяформированиеодного из допустимых решений. Неиспользованный остаток объема в единицпозволяет поместить только один предмет первого типа. В окончательном решении, соответствующемэтомумаршруту,стоимость предметов, уложенных в рюкзак, равна

Несложно заметить, что разобранный маршрутне соответствуетоптимальному решению. Оптимальным будетрешение , асоответствующая ему стоимость – Этапы этогорешенияна рис. 7.4обозначены закрашеннымиовалами.

Из схемы, приведенной на рис. 4,видно, что врекурсивном решении,как и в случае сиспользованием генератора, осуществляетсяполный перебор допустимых решений.

На рис. 5 и 6 представлена функция knapsack_r, реализующая рекурсивный алгоритм решения задачи о рюкзаке.

Рис.5.Прототип функции knapsack_r

Функция knapsack_rимеет четыре входных и один возвращаемыйпараметры:значениевходных параметровзадают условиезадачи, апоследнийвозвращаемый параметр mпредставляетсобой массив размерностьюn(общее количество предметов, заданное вторым параметром),содержащий количествавыбранных предметов каждого типа.

Рис. 6.Реализация рекурсивнойфункции knapsack_r

Условнотекст функции knapsack_rможноразбить на дваблока, соответствующихдвум ветвямоператора if-else.

В первом блокев цикле осуществляется рекурсивный вызов функцииknapsack_r. В цикле в порядке возрастания перебираются все допустимые для заданного неиспользованного объема рюкзакаколичества предметов одного типа.Вызов функции knapsack_rв итерации цикла соответствует разветвлению вузлахграфана рис. 4.

Кроме массива m, содержащего количества предметов каждого типа в оптимальнойзагрузке рюкзака, функция в точку вызова возвращаетсуммарную стоимостьэтихпредметов.

Во втором блоке обрабатывается так называемоедно рекурсии. Дно рекурсии соответствует последнему вызову функции knapsack_r(последнему этапу решения)вполнойветви графа на рис. 4.

На рис. 7 и8 приведенпример вызова функции knapsack_rдля решения задачи о рюкзакестакимиже исходнымиданными,чтодлясхемы, представленной на рис. 4.

Рис. 7.Пример вызовафункции knapsack_r

Рис. 8.Результат выполнения программы, представленной на рис. 7