Задача о рюкзаке. Динамическое программирование
Опишем алгоритм решения задачи о рюкзаке, основанный на методе динамического программирования. Пусть коэффициенты в удовлетворяют соотношениям:cj>0, aj>0, b>0, cj∈Z, aj∈Z, b∈Z, (j=1,2,..,n)
Легко видеть, что тогда множество допустимых векторов задачи ограничено и не пусто (x1 = x2 = ... = xn = 0).
Для каждого k∈{1,2,...,n} и y∈{1,2,...,b} рассмотрим вспомогательную задачу о рюкзаке
оптимальное значение целевой функции которой обозначим fk(y). Заметим, что fn(b) равно искомому оптимальному значению целевой функции исходной задачи (81). Ниже мы получим рекуррентные соотношения, выражающие значение функции fk(y) через ее значения при меньших k и y. На основе этих соотношений можно организовать процесс, позволяющий для всех k и y найти fk(y), в том числе fn(b). В этом заключается основная идея метода.
Рассмотрим задачу (105) при k = 1. В ней требуется разместить в рюкзак грузоподъемности y максимальное число предметов первого типа. Очевидно, что
f1(y)=c1·[y/a1] (y=1,2,...,b)
Рассмотрим теперь задачу (105) при k > 1. Требуется разместить в рюкзак предметы первых k типов, так, чтобы суммарная ценность груза была бы максимальна. Предположим, что рюкзак заполнен оптимально.
Если в рюкзаке нет ни одного предмета k-го типа, то он заполнен только предметами типов 1,2,... ,k - 1. Так как заполнение оптимально, то значение целевой функции (суммарная ценность) в этом случае равна fk(y) = fk-1(y).
Если в рюкзаке предмет k-го типа находится только в одном экземпляре, то оставшееся место y — ak должно быть заполнено оптимальным образом предметами типов 1,2,... ,k — 1. В этом случае fk(y) = fk-1(y - ak) + ck.
Если в рюкзаке два предмета k-го типа, то под остальные предметы остается место равное y - 2ak. Так как заполнение оптимально, то
fk(y) = fk-1(y-2ak) + 2ck.
Эти рассуждения можно провести далее, рассмотрев случаи с тремя, четырьмя и т. д. предметами k-го типа, находящимися в рюкзаке, вплоть до случая, когда в рюкзаке находится максимально возможное число [y/ak] предметов k-го типа. Оставшееся место y - ak · [y/ak] должно быть заполнено оптимальным образом предметами первых (k - 1) типов. Получаем
fk(y) = fk-1(y - ak · [y/ak]) + ck · [y/ak].
Подводя итог вышесказанному, можно сделать вывод, что
fk(y-ak) = max{fk-1(y-ak),...,fk-1(y-ak·[y/ak])+ck·[y/ak]-ck}
Теперь ясно, что в соотношении (107) все элементы, среди которых ищется максимальный, кроме первого, можно заменить на fk(y - ak) + ck, т. е.fk(y) = max{fk-1(y), fk(y-ak)+ck} (k=2,...,n; y=ak+1,...,b) (108)
Вычисления проводятся по формулам (106) и (108) (при y < 0 положим fk(y) = -∞). Удобно использовать таблицу F размера n x b. В k-ой строке и y-ом столбце этой таблицы записывается значение fk(y). Таблица заполняется по строкам сверху вниз, в каждой строке слева направо. Заметим, что для вычисления fk(y) достаточно знать fk-1(y) и fk(y - ak). Это позволяет хранить только одну строку таблицы F.Для того, чтобы кроме оптимального значения целевой функции найти компоненты решения, используют другую таблицу I. Таблица I также имеет размеры n x b и заполняется следующим образом. В k-ой строке и y-ом столбце этой таблицы записывается максимальной номер i(k,y) ненулевой компоненты оптимального вектора задачи (105), т. е.
Пример. Решим задачу
max(8x1+5x2+x3)
3x1+2x2+x3≤13
x∈Z, x≥0 (j=1,2,3)
методом динамического программирования.
По формулам (106) и (108) вычислим элементы таблицы F:
i(3,13)=2
i(3,13-a2)=i(3,11)=2
i(3,11-a2)=i(3,9)=1
i(3,9-a1)=i(3,6)=1
i(3,6-a1)=i(3,6)=1
Таким образом, оптимальный вектор имеет компоненты x1 = 3, x2 = 2, x3 =0.