Bitmask DP: как покрыть множество минимальным числом заданных подмножеств (set cover перебором)?
Есть универсум из $n \le 20$ элементов и список подмножеств (каждое задано битовой маской). Нужно покрыть весь универсум минимальным числом этих подмножеств (можно с повторами). Set cover NP-труден в общем, но при $n \le 20$ должен решаться ДП по маске покрытых элементов. Как?
2 ответа
Состояние — маска уже покрытых элементов. dp[mask] = минимальное число подмножеств, чтобы покрыть ровно элементы из mask (как надмножество — нам нужно покрыть всё, поэтому достаточно дойти до full). Это BFS/ДП по $2^n$ состояниям.
int n;
vector<int> subsets; // маски доступных подмножеств
int FULL = (1 << n) - 1;
vector<int> dp(1 << n, INT_MAX);
dp[0] = 0;
for (int mask = 0; mask <= FULL; ++mask) {
if (dp[mask] == INT_MAX) continue;
for (int s : subsets) {
int nmask = mask | s; // добавили подмножество s
if (dp[nmask] > dp[mask] + 1)
dp[nmask] = dp[mask] + 1;
}
}
// ответ dp[FULL]
Сложность $O(2^n \cdot |subsets|)$ времени, $O(2^n)$ памяти. При $n=20$ и нескольких сотнях подмножеств это $\sim 10^6 \cdot 10^2 = 10^8$ — на грани, но проходит при аккуратной реализации.
Так как все рёбра «стоят 1», это по сути поиск кратчайшего пути в графе масок — можно заменить ДП на BFS (он гарантирует обработку в порядке возрастания числа шагов и даёт тот же результат за $O(2^n \cdot |subsets|)$).
Оптимизация, которая часто спасает от TLE: для каждой маски перебирать подмножества, покрывающие первый непокрытый элемент. Берём младший непокрытый бит i = __builtin_ctz(~mask & FULL) и пробуем только те s, у которых бит i стоит. Это режет ветвление и не теряет оптимальности (этот элемент всё равно надо кем-то покрыть).
int i = __builtin_ctz(~mask & FULL); // первый непокрытый
for (int s : subsets) if (s & (1 << i)) { ... }
Ещё: предварительно выкинь подмножества, являющиеся подмножеством другого — они никогда не лучше. И помни, что если покрыть нельзя (есть элемент, не входящий ни в одно подмножество), dp[FULL] останется INT_MAX — это надо корректно обработать в выводе.