Dynamic Programming
Bitmask Dynamic Programming
Written by Swapnil RajaPublished
When a subproblem is identified by "which of these n things have I used", the state is a subset - and a subset of at most about twenty items fits neatly in a single integer.
A set as a number
Bit i set means item i is in the set. With n items there are 2ⁿ possible subsets, and each is just an integer from 0 to 2ⁿ − 1 - which makes them perfect array indices, and makes comparing or copying a state a single machine operation.
Working with subset masks
javascript
const n = 4
// Is item i in the set?
const has = (mask, i) => (mask & (1 << i)) !== 0
// Add and remove.
const add = (mask, i) => mask | (1 << i)
const remove = (mask, i) => mask & ~(1 << i)
// Every subset of n items.
for (let mask = 0; mask < (1 << n); mask++) {
const members = []
for (let i = 0; i < n; i++) if (has(mask, i)) members.push(i)
if (mask < 5) console.log(mask, members)
}
const full = (1 << n) - 1 // all items present
console.log("full set:", full, full.toString(2))