Перебор всех подмасок данной маски

Давайте решим такую задачу: Есть множество из $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$ те элементы, которые не принадлежат маске.

1 dp[0] = 0;
2 for (int mask = 1; mask < (1 << n); mask++) {
3     for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
4         dp[mask] = max(dp[mask], dp[mask ^ submask] + cost[submask];
5     }
6 }

---

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s