Bitset Optimization

Bitset Optimization

Idea

std::bitset (or your own bitset on uint64_t) lets us process many boolean states in one operation.

Instead of updating DP / transitions one cell at a time, we update 64 bits at once (or another machine-word block size), so the constant factor improves a lot.

This is very useful when:

• DP state is boolean (reachable / not reachable)
• transitions can be expressed with shifts / OR / AND
• constraints are large enough that constants matter

Example 1

Problem

Given $N$ items. Item $i$ has weight $w_i$. Check if there is a subset with total weight exactly $W$.

Classic DP

Let d[j] = 1 if sum j is reachable.

Bitset Optimization