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

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

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

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

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

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

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

, ,

, …, , .

Схема решения задачи о рюкзаке с помощью рекурсивного алгоритма при , изображена на рис. 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.