Оптимизация битового набора

Оптимизация битового набора

Идея

std::bitset (или ваш собственный bitset на uint64_t) позволяет обрабатывать много булевых состояний за одну операцию.

Вместо обновления DP / переходов по одной ячейке за раз, мы обновляем 64 бита за раз (или другой размер блока машинного слова), поэтому константный множитель сильно улучшается.

Это очень полезно, когда:

• состояние DP булево (достижимо / недостижимо)
• переходы можно выразить сдвигами / OR / AND
• ограничения достаточно большие, что константы имеют значение

Пример 1

Задача

Дано $N$ предметов. Предмет $i$ имеет вес $w_i$. Проверить, существует ли подмножество с суммарным весом ровно $W$.

Классическое DP

Пусть d[j] = 1, если сумма достижима.