Динамика по подмножествам

Если в задаче есть до двадцати объектов и важно, какие из них уже использованы, состоянием динамики становится маска.

Работает это потому, что подмаска в порядке возрастания встречается раньше маски: обычный цикл for (int mask = 0; mask < (1 << n); mask++) уже даёт правильный порядок вычислений, и ни рекурсия, ни топологическая сортировка не нужны.

Коммивояжёр

Классика жанра. $dp[mask][v]$ — наименьшая стоимость пути, который начался в вершине 0, посетил ровно вершины из $mask$ и закончился в $v$.

dp[1][0] = 0;
for (int mask = 1; mask < (1 << n); mask++)
    for (int v = 0; v < n; v++) {
        if (dp[mask][v] >= INF || !(mask >> v & 1)) continue;
        for (int to = 0; to < n; to++) {
            if (mask >> to & 1) continue;
            int next = mask | (1 << to);
            dp[next][to] = std::min(dp[next][to], dp[mask][v] + d[v][to]);
        }
    }

Стоит это $O(2^n n^2)$ по времени и $O(2^n n)$ по памяти. Замеры: $n = 16$ — 23 мс, $n = 18$ — 85 мс, $n = 20$ — 405 мс. То есть двадцать вершин проходят с запасом, а двадцать две уже нет.

Память при $n = 20$: $2^{20} \cdot 20$ чисел по четыре байта — 80 мегабайт. Это уже близко к типичному ограничению, и часто именно память, а не время, ставит границу.

Другие типовые задачи

задача	состояние
разбить на пары с наименьшей суммой	маска использованных
назначить $n$ работ $n$ исполнителям	маска занятых исполнителей
покрыть множество наименьшим числом подмножеств	маска покрытого
раскрасить граф в наименьшее число цветов	маска покрашенных

В задаче о разбиении на пары полезен приём: не перебирать оба элемента пары, а всегда брать наименьший невыбранный. Это убирает лишний множитель $n$.

int first = __builtin_ctz(~mask & full);          // наименьший свободный
for (int second = first + 1; second < n; second++)
    if (!(mask >> second & 1)) { ... }

Когда $2^n$ не хватает

Иногда состояние — не «какие использованы», а «сколько чего осталось». Если объектов много, но типов мало, вместо маски берут вектор счётчиков — и получается динамика по профилю.

А если нужно перебрать разбиения на подмножества, помогает перебор подмасок: $\sum_{mask} 2^{|mask|} = 3^n$, что при $n \le 18$ ещё живо.

Смежное

• Маска как множество;
• Подмаски;
• Динамика: что это.