Partition: как проверить разбиение на два подмножества равной суммы битсетом?
Задача partition: можно ли разбить массив на два подмножества с равной суммой. Это subset-sum на total/2. Обычное булево ДП dp[s] за O(n·S) местами медленновато. Слышал, что std::bitset ускоряет в ~64 раза. Как это применить?
2 ответа
Идея: булево ДП subset-sum dp[s] = можно ли набрать сумму s — это битовый вектор. Добавление числа x означает «все достижимые суммы плюс x тоже достижимы», то есть сдвиг битсета влево на x и OR с собой. std::bitset делает это за O(S/64).
int total = accumulate(a.begin(), a.end(), 0);
if (total % 2) { /* нечётное — разбить нельзя */ }
int half = total / 2;
bitset<MAXSUM> dp; // MAXSUM > half
dp[0] = 1; // пустое подмножество даёт сумму 0
for (int x : a) dp |= (dp << x);
bool can = dp[half];
Сложность O(n·S/64) время, O(S/64) память — то самое ускорение в ~64 раза против наивного O(n·S). MAXSUM (размер bitset) должен быть константой времени компиляции и больше half. Грабля: если total нечётное — сразу ответ «нет», иначе half дробное.
Несколько предостережений. bitset<N> требует N константой времени компиляции — нельзя bitset<n> с переменной; бери запас, например bitset<100001>, под максимально возможную половину суммы из условия. Если суммы реально огромные (S ~ 10^9), bitset не влезет в память — тогда возвращайся к meet-in-the-middle по n. И помни: dp << x создаёт временный битсет, для очень больших N это не бесплатно по памяти, но укладывается. Этот же приём (битсет-сдвиг) работает для любого булева subset-sum, не только partition.