4.3. Задача грабителя (задача о рюкзаке)

Задача. Имеется склад, на котором есть некоторый ассортимент товаров. Запас каждого товара считается неограниченным. Товары имеют две характеристики: m_i – масса, c_i – стоимость;

Необходимо выбрать набор товаров так, что бы его суммарная масса не превосходила заранее фиксированную массу М(т.е. Σm_i ≤ M), и стоимость набора была как можно больше (Σc_i→max).

Идея решения. Считаем, что все массы m_i целочисленные. Решим эту задачу методом динамического программирования. Изобретаем метод, т.е. формулу.

Нам необходимо найти f(M), т.е. максимально возможную сумму m_i при заданном М. Предположим, что к этому моменту мы знаем, как решать эту задачу для всех меньших значений грузоподъемности. Тогда смотрим, какой товар мы положили в рюкзак предпоследним. Если это был первый товар стоимость c₁, то мы должны оптимизировать стоимость рюкзака при грузоподъемности M – m₁. Если это был второй товар стоимость c₂, то оптимизация при грузоподъемности M – m₂, и т.д. Среди этих величин выбираем максимальную.

Таким образом, получаем формулу:

Пример. Рассмотрим решение этой задача при следующем наборе товаров:

Решение.

Вычислим последовательно:

f(0) = 0; f(1) = 0; f(2) = 0; f(3) = 8; f(4) = 8;

f(5) = 14 = max(f(5-3)+8; f(5-5)+14; f(5-8)+23); - не рассматриваем при поиске максимума, так как f(-3) не определена.

f(6) = 16; f(7) = 16; f(8) = 23; f(9) = 24 = max(f(9-3)+8; f(3-5)+14; f(9-8)+23);

f(10) = 28; f(11) = 31; f(12)= 32; f(13) = 37 = max(f(13-3)+8; f(13-5)+14; f(13-8)+23).

Оценим трудоемкость решения задачи о рюкзаке методом ДП.

Для применения метода ДП все массы должны быть целочисленные (а стоимости – необязательно). Тогда если k – количество видов товаров, m – грузоподъемность, то имеем m шагов внешнего цикла (по грузоподъемности) и на каждом шаге находим максимум среди k чисел, каждое из которых является суммой двух слагаемых. В итоге получаем трудоемкость: T = m·k.