Перейти к содержанию

10.5 Динамическое программирование

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

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

Оптимальный выбор

Рассмотрим задачу. Есть k товаров и n дней. Для каждого товара известна его цена в каждый день. Нужно купить каждый товар ровно один раз, причём за один день можно купить не более одного товара. Требуется минимизировать суммарную стоимость.

Возьмём пример с тремя товарами и восемью днями:

День 0 1 2 3 4 5 6 7
Товар 0 7 5 8 2 9 6 3 8
Товар 1 6 3 7 4 5 8 2 6
Товар 2 5 6 4 7 3 5 1 4

Один из оптимальных вариантов:

  • товар 0 купить в день 3 за 2,
  • товар 1 купить в день 6 за 2,
  • товар 2 купить в день 4 за 3.

Тогда общая стоимость равна 2 + 2 + 3 = 7.

Состояние динамики

Обозначим через price[x][d] цену товара x в день d.

Пусть total(S, d) — минимальная суммарная стоимость покупки всех товаров из множества S не позднее дня d.

Тогда ответом будет:

\[ total({0,1,\dots,k-1},; n-1). \]

Базовые случаи

Пустое множество ничего не стоит:

\[ total(\varnothing, d) = 0. \]

Если в множестве только один товар x, а доступен только день 0, то его можно купить только в этот день:

\[ total({x}, 0) = price[x][0]. \]

Переход

Для состояния total(S, d) есть две возможности:

  1. ничего не покупать в день d,
  2. купить в день d некоторый товар x \in S.

Поэтому переход имеет вид:

\[ total(S,d)=\min\left( total(S,d-1), \min_{x\in S}\bigl(total(S\setminus{x}, d-1)+price[x][d]\bigr) \right). \]

Смысл формулы простой: если в день d покупается товар x, то до этого дня нужно было уже оптимально купить все товары из множества S \setminus \{x\}.

Реализация

Если кодировать множество S битовой маской, можно хранить значения в массиве:

int total[1<<K][N];

Здесь первая размерность — это маска подмножества товаров.

Начальные значения для дня 0:

for (int x = 0; x < k; x++) {
    total[1<<x][0] = price[x][0];
}

Далее заполняем таблицу по дням:

for (int d = 1; d < n; d++) {
    for (int s = 0; s < (1<<k); s++) {
        total[s][d] = total[s][d-1];
        for (int x = 0; x < k; x++) {
            if (s & (1<<x)) {
                total[s][d] = min(total[s][d],
                    total[s ^ (1<<x)][d-1] + price[x][d]);
            }
        }
    }
}

Сложность

Всего состояний n · 2^k, и в каждом состоянии мы перебираем до k товаров. Поэтому итоговая сложность:

\[ O(n \cdot 2^k \cdot k). \]

От перестановок к подмножествам

Во многих задачах кажется естественным перебирать все перестановки. Но часто это слишком дорого: n! растёт очень быстро. Если удаётся заменить такой перебор на динамику по подмножествам, то сложность уменьшается до O(2^n \cdot \text{poly}(n)), а это уже совсем другой уровень.

Например, при n = 20:

  • 20! \approx 2.4 \cdot 10^{18},
  • 2^{20} \approx 10^6.

Разница огромная.

Задача про лифт

Есть лифт грузоподъёмностью x и n человек с известными весами. Нужно перевезти всех с первого этажа наверх, минимизировав число поездок. Порядок посадки можно выбирать как угодно.

Пример:

Человек Вес
0 2
1 3
2 3
3 5
4 6

Если x = 10, то достаточно двух поездок. Например:

  • первая поездка: {0, 2, 3} с общим весом 10,
  • вторая поездка: {1, 4} с общим весом 9.

Почему не стоит перебирать порядок

Можно было бы перебрать все возможные порядки посадки людей, но это даёт сложность порядка O(n! · n). Намного лучше рассматривать не порядок, а подмножество людей, которых уже перевезли.

Состояние

Для каждого подмножества S будем хранить пару значений:

  • rides(S) — минимальное число поездок,
  • last(S) — минимально возможный суммарный вес людей в последней поездке среди всех оптимальных решений.

То есть состояние — это не одно число, а пара.

Например, если S = {1,3,4}, то можно получить:

  • rides(S) = 2,
  • last(S) = 5.

Это означает, что людей из множества S можно перевезти за две поездки, и при этом вес последней поездки можно сделать равным 5.

Идея перехода

Пусть мы хотим вычислить состояние для множества S. Выберем человека p, который заходит в лифт последним. Тогда до него уже было оптимально обработано множество S \setminus \{p\}.

Если человек p помещается в последнюю поездку, то просто добавляем его туда. Иначе начинаем новую поездку.

Реализация

Будем хранить для каждой маски пару:

pair<int,int> best[1<<N];

Для пустого множества:

best[0] = {1,0};

Это удобно интерпретировать как «одна пустая поездка, текущий вес 0».

Основной переход:

for (int s = 1; s < (1<<n); s++) {
    best[s] = {n+1, 0};
    for (int p = 0; p < n; p++) {
        if (s & (1<<p)) {
            auto option = best[s ^ (1<<p)];
            if (option.second + weight[p] <= x) {
                option.second += weight[p];
            } else {
                option.first++;
                option.second = weight[p];
            }
            best[s] = min(best[s], option);
        }
    }
}

Сравнение пар идёт лексикографически:

  • сначала минимизируется число поездок,
  • при равенстве — вес последней поездки.

Это и даёт корректный выбор оптимального состояния.

Почему порядок вычисления верный

Когда обрабатывается маска s, все маски вида s ^ (1<<p) уже меньше по количеству битов. Значит, их значения уже посчитаны. Именно поэтому динамика по подмножествам здесь работает естественно.

Сложность

Масок 2^n, и для каждой мы перебираем n вариантов последнего человека. Следовательно, сложность равна:

\[ O(2^n n). \]

Подсчёт по всем подмножествам

Разберём ещё одну важную идею. Пусть

\[ X = {0,1,\dots,n-1}, \]

и каждому подмножеству S \subseteq X сопоставлено значение value[S].

Для каждого множества S нужно вычислить:

\[ sum(S)=\sum_{A\subseteq S} value[A], \]

то есть сумму значений всех подмножеств множества S.

Пример

Пусть n = 3 и заданы значения:

  • value[∅] = 3
  • value[{0}] = 1
  • value[{1}] = 4
  • value[{0,1}] = 5
  • value[{2}] = 5
  • value[{0,2}] = 1
  • value[{1,2}] = 3
  • value[{0,1,2}] = 3

Тогда, например,

\[ sum({0,2}) = value[\varnothing] + value[{0}] + value[{2}] + value[{0,2}] = 3+1+5+1=10. \]

Наивный подход

Можно для каждого множества S перебрать все его подмножества A. Но тогда получится слишком дорого: порядка O(2^{2n}).

Идея динамики

Введём вспомогательную функцию partial(S, k) — сумму значений таких подмножеств множества S, из которых разрешено удалять только элементы 0,1,...,k.

Например,

\[ partial({0,2},1)=value[{2}] + value[{0,2}], \]

потому что здесь можно удалить только элементы 0 и 1, а элемент 2 трогать нельзя.

Тогда окончательный ответ выражается так:

\[ sum(S)=partial(S,n-1). \]

База

Если запрещено удалять вообще какие-либо элементы, остаётся только само множество S:

\[ partial(S,-1)=value[S]. \]

Переход

Смотрим на элемент k.

  • Если k \notin S, то ничего не меняется:
\[ partial(S,k)=partial(S,k-1). \]

  • Если k \in S, то есть два варианта:

  • оставить k,

  • удалить k.

Поэтому:

\[ partial(S,k)=partial(S,k-1)+partial(S\setminus{k},k-1). \]

Это классическая динамика по битам множества.

Очень компактная реализация

Можно обойтись вообще одним массивом:

int sum[1<<N];

Сначала копируем исходные значения:

for (int s = 0; s < (1<<n); s++) {
    sum[s] = value[s];
}

Затем последовательно «разрешаем удалять» очередной бит:

for (int k = 0; k < n; k++) {
    for (int s = 0; s < (1<<n); s++) {
        if (s & (1<<k)) {
            sum[s] += sum[s ^ (1<<k)];
        }
    }
}

После завершения цикла sum[s] уже будет равно

\[ \sum_{A\subseteq S} value[A]. \]

Почему это работает

Когда у маски s установлен бит k, выражение

sum[s ^ (1<<k)]

соответствует случаю, где элемент k удалён. А текущее sum[s] соответствует случаю, где элемент k оставлен. Складывая их, мы объединяем оба варианта.

Этот приём часто называют SOS DP (sum over subsets dynamic programming).

Сложность

Есть n шагов по битам и 2^n масок. Поэтому сложность:

\[ O(n2^n). \]

Что важно вынести из раздела

Когда состояние задачи можно описать подмножеством элементов, битовая маска часто оказывается самым удобным представлением. Это даёт несколько очень полезных шаблонов:

  1. DP по маске и дополнительному параметру — как в задаче о покупке товаров по дням.
  2. Замена перебора перестановок перебором подмножеств — как в задаче про лифт.
  3. Суммирование или агрегирование по всем подмножествам — как в SOS DP.

Во всех этих случаях ключевая идея одна и та же: множество кодируется числом, а переходы между состояниями выполняются побитовыми операциями вроде

s & (1<<x)
s ^ (1<<x)

Это делает код компактным и обычно заметно ускоряет реализацию.

Если затем встретится задача на гамильтонов путь, коммивояжёра, распределение объектов, упаковку, оптимальный порядок действий или суммирование по подмножествам, очень часто стоит первым делом проверить: не подходит ли здесь динамика по битовой маске?