Перебор подмасок фиксированной маски
Дана битовая маска m. Требуется эффективно перебрать все её подмаски, т.е. такие маски s, в которых могут быть включены только те биты, которые были включены в маске m.
Сразу рассмотрим реализацию этого алгоритма, основанную на трюках с битовыми операциями:
int s = m; while (s > 0) { … можно использовать s … s = (s-1) & m; } или, используя более компактный оператор for:
for (int s=m; s; s=(s-1)&m) … можно использовать s … Единственное исключение для обоих вариантов кода — подмаска, равная нулю, обработана не будет. Её обработку придётся выносить из цикла, или использовать менее изящную конструкцию, например:
for (int s=m; ; s=(s-1)&m) { … можно использовать s … if (s==0) break; } Разберём, почему приведённый выше код действительно находит все подмаски данной маски, причём без повторений, за O (их количества), и в порядке убывания.
Пусть у нас есть текущая подмаска s, и мы хотим перейти к следующей подмаске. Отнимем от маски s единицу, тем самым мы снимем самый правый единичный бит, а все биты правее него поставятся в 1. Затем удалим все “лишние” единичные биты, которые не входят в маску m и потому не могут входить в подмаску. Удаление осуществляется битовой операцией \& m. В результате мы “обрежем” маску s-1 до того наибольшего значения, которое она может принять, т.е. до следующей подмаски после s в порядке убывания.
Таким образом, этот алгоритм генерирует все подмаски данной маски в порядке строгого убывания, затрачивая на каждый переход по две элементарные операции.
Особо рассмотрим момент, когда s = 0. После выполнения s-1 мы получим маску, в которой все биты включены (битовое представление числа -1), и после удаления лишних битов операцией (s-1) \& m получится не что иное, как маска m. Поэтому с маской s = 0 следует быть осторожным — если вовремя не остановиться на нулевой маске, то алгоритм может войти в бесконечный цикл.
Перебор всех масок с их подмасками. Оценка 3^n Во многих задачах, особенно на динамическое программирование по маскам, требуется перебирать все маски, и для каждой маски - все подмаски:
for (int m=0; m<(1<<n); ++m) for (int s=m; s; s=(s-1)&m) … использование s и m … Докажем, что внутренний цикл суммарно выполнит O (3^n) итераций.
Доказательство: 1 способ. Рассмотрим i-ый бит. Для него, вообще говоря, есть ровно три варианта: он не входит в маску m (и потому в подмаску s); он входит в m, но не входит в s; он входит в m и в s. Всего битов n, поэтому всего различных комбинаций будет 3^n, что и требовалось доказать.
Доказательство: 2 способ. Заметим, что если маска m имеет k включённых битов, то она будет иметь 2^k подмасок. Поскольку масок длины n с k включёнными битами есть C_n^k (см. “биномиальные коэффициенты”), то всего комбинаций будет:
\sum_{k=0}^n C_n^k 2^k.
Посчитаем эту сумму. Для этого заметим, что она есть не что иное, как разложение в бином Ньютона выражения (1+2)^n, т.е. 3^n, что и требовалось доказать.
Давайте решим такую задачу: Есть множество из $n$ элементов, мы должны отнести каждый элемент к какому-то классу, минимизировав суммарную стоимость классов. Стоимостью класса называется стоимость множества всех элементов, стоимость множества элементов подается на вход как $cost_{subset},\\ 0 \\le subset \\le 2^n$. Для решения такой задачи можно использовать динамику вида $dp_{mask} = \displaystyle \max_{subset\ \subset\ mask} cost_{subset} + dp_{mask \setminus subset}$. Решение “в лоб”, перебирающее все пары двоичных масок, будет работать за $O(4^n)$.
Идея
Если перебирать в качестве $subset$ не все маски, а только подмаски $mask$, то суммарное время работы значительно уменьшится. Почему? Давайте посмотрим на один переход динамики — у нас имелись $subset,\\ mask \\setminus subset$. Тогда множество распадалось на три части: элементы из $subset$, элементы из $mask \\setminus subset$, и не попавшие никуда элементы. При этом каждому разбиению будет соответствовать ровно один переход динамики. А число способов разделить множество на три класса — это $3^n$. Таким образом, такой алгоритм будет работать за $O(3^n)$
Реализация
Осталось разобраться, как эффективно перебрать все подмаски данной маски. Придумаем такой алгоритм. Сначала позьмем полное подмножество. Дальше мы будем уменьшать двоичное число на 1, соответствующее маске, после чего обнулять все биты, которые не принадлежали маске. Что происходит в такой ситуации?
Если последняя единичка в двоичной записи $subset$ была на позиции $x$, то $(subset - 1) \\& mask$ будет содержать все единички $subset$ слева от $x$, и все единички $mask$ справа от $x$. Таким образом, для каждой подмаски мы слева направо постепенно удалим из $mask$ те элементы, которые не принадлежат маске.
dp[0] = 0;
for (int mask = 1; mask < (1 << n); mask++) {
for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
dp[mask] = max(dp[mask], dp[mask ^ submask] + cost[submask];
}
}