Задача о рюкзаке. Динамическое программирование

Опишем алгоритм решения задачи о рюкзаке, основанный на методе динамического программирования. Пусть коэффициенты в удовлетворяют соотношениям:

Легко видеть, что тогда множество допустимых векторов задачи ограничено и не пусто (x1 = x2 = ... = xn = 0).
Для каждого и рассмотрим вспомогательную задачу о рюкзаке

оптимальное значение целевой функции которой обозначим fk(y). Заметим, что fn(b) равно искомому оптимальному значению целевой функции исходной задачи (81). Ниже мы получим рекуррентные соотношения, вы­ражающие значение функции fk(y) через ее значения при меньших k и y. На основе этих соотношений можно организовать процесс, позволяющий для всех k и y найти fk(y), в том числе fn(b). В этом заключается основная идея метода.
Рассмотрим задачу (105) при k = 1. В ней требуется разместить в рюкзак грузоподъемности y максимальное число предметов первого типа. Очевидно, что

Рассмотрим теперь задачу (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].
Подводя итог вышесказанному, можно сделать вывод, что

Упростим рекуррентное соотношение (107). Для этого вначале вместо y в него подставим y - ak. Получим

Теперь ясно, что в соотношении (107) все элементы, среди которых ищется максимальный, кроме первого, можно заменить на fk(y - ak) + ck, т. е.

Вычисления проводятся по формулам (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), т. е.

Пример. Решим задачу

методом динамического программирования.
По формулам (106) и (108) вычислим элементы таблицы F:

Оптимальное значение целевой функции ЗЦЛП (110) равно f3(13) = 34. По формулам (109) вычислим:

Для восстановления компонент решения в таблице I найдем

Таким образом, оптимальный вектор имеет компоненты x1 = 3, x2 = 2, x3 =0.

Перейти к онлайн решению своей задачи

Открыть диалог Discus Помощь в решении контрольных