Рассмотрим еще одну задачу, решаемую схемой возвратной рекурсии, для которой заранее не известна длина получаемого решения.
адача
12. Задача о рюкзаке.
Имеются m предметов с
номерами от 0 до m-1,
для каждого из которых известна масса в
килограммах pj
и стоимость cj (j = 0,1,…,m-1).
Определить, какие предметы необходимо
положить в рюкзак, чтобы их общая масса не
превышала Q килограммов,
а общая стоимость была максимальной.
Решением задачи может служить пара функций Ks(PC, Q, ne, pos, ot, j) и Ksack(PC, Q):
Головная функция Ksack(PC, Q) по матрице PC и величине Q подготавливает фактические аргументы для рекурсивной функции Ks():
 |
ne = (-1, -1, …, -1, 0, 0) - вектор длины m+2 для записи частичного или окончательного решения задачи (последовательности предметов, их общей массы и стоимости); |
|
pos - нулевой вектор меток длины m для указания уже отобранных для рюкзака предметов; |
|
ot = (0, 0, …, 0, 0, 0) - вектор длины m+2 для записи из ne текущего частичного или окончательного решения задачи; |
|
j = 0 - номер рекурсивного вызова. |
Параметры функции Ks(PC, Q, ne, pos, ot, j) имеют следующий смысл:
|
PC - матрица масс и стоимостей предметов; | ||
|
Q - верхняя граница общей массы предметов, размещаемых в рюкзаке; | ||
|
ne - вектор длины m+2 для записи номеров формируемой для решения последовательности предметов (компоненты от 0 до m-1), а также их общей массы (компонент m) и стоимости (компонент m+1); | ||
|
pos - вектор меток. Если предмет i в j-м рекурсивном вызове подключается к решению (nej¬i), то в векторе меток этот факт фиксируется следующим образом: poi¬1. При переходе к предыдущему рекурсивному уровню или к рассмотрению следующего предмета единичная метка удаляется: poi=0; | ||
|
ot - вектор, в который при otm+1<nem+1 из ne переписывается текущее частичное или окончательное решение задачи (при i = otj > 0 (j = 0, 1, …, m-1) предмет i включен в решение, при i=-1 - нет);
| j - уровень рекурсивного вызова. |
Остановимся вкратце на алгоритме, реализуемом функцией Ks(), и динамике формирования последовательности предметов для рюкзака. Рекурсия организована по j - порядковому номеру (от нуля и далее) укладываемого в рюкзак предмета (см. рис.8). В каждом вызове глубины j делается попытка расширить частичное решение за счет i-го предмета (i, j = 0, 1, …, m-1). При этом параметр i меняется от нуля и далее с шагом, равным единице, пытаясь принять значение наименьшего номера предмета, допустимого для расширения частичного решения. При переходах к любому предыдущему рекурсивному вызову параметр i продолжает изменяться от своего текущего на данном уровне значения с шагом, равным единице, также пытаясь принять значение наименьшего номера предмета, допустимого для расширения частичного решения. Если в текущем рекурсивном вызове построенное частичное решение изменить уже нельзя, то происходит возврат к предыдущему вызову. При возврате из уровня j=0 вычисления прекращаются, но к этому моменту решение задачи уже получено и находится в векторе ot.
Рис. 8. Опорная схема для описания рекурсии в задаче о рюкзаке
Контрольные примеры. Пусть матрица масс предметов и их стоимостей имеет следующий вид:
На рисунке 9 приведены результаты вычислений по функции Ksack(M, Q) при Q=7 и Q=21 и дана их интерпретация.
Замечание. Функция Ksack(), кроме решения, выдает некоторый “мусор” - минус единицы. Они специально не удалены из решения из дидактических соображений, ибо возвращаемый в таком виде вектор несет в себе “следы работы алгоритма”, что, несомненно, способствует его лучшему пониманию.
Существенного ускорения вычислений можно достичь, если снабдить функцию Ks() дополнительным параметром be и использовать его в рекурсивных вызовах следующим образом. При начальном обращении к Ks() считать be=0. Далее, если на некотором рекурсивном вызове в частичное решение включен предмет i, то при переходе к следующему рекурсивному уровню необходимо положить be=i+1. Именно это значение (а не нуль) и использовать в качестве начального номера предмета при попытке дальнейшего расширения частичного решения. Заметим, что в этом случае становится совершенно ненужным вектор меток pos, в котором ранее отмечались номера подключаемых к частичному решению предметов. Осуществление указанных преобразований функций Ks() и Ksack() приводит к такой их модификации:
Контрольный пример. Пусть матрица масс предметов и их стоимостей имеет следующий вид:
Тогда
