🎓 A1Learner
🔍
0 of 93 lessons completed

DSA Bitmask DP

Bitmask DP is dynamic programming where a set is carried as bits inside one integer. Each bit says whether one item is already used.

Bits form a tiny set

A mask of 13 has bits 0, 2 and 3 set. Those bits name items 0, 2 and 3.

mask = 0b1101
print('mask', mask)
for i in range(4):
    print(i, bool(mask & (1 << i)))

Adding one unused item

Setting a bit adds one item to the set. Testing a bit checks membership in one step.

mask = 0b0101
print('has 1', bool(mask & (1 << 1)))
mask = mask | (1 << 1)
print('after add', bin(mask))
print('count', bin(mask).count('1'))

One assignment step

A state counts the workers already placed. The popcount of the mask gives that count.

cost = [[9, 2], [6, 4]]
mask = 0b01
worker = bin(mask).count('1')
for job in range(2):
    if not mask & (1 << job):
        print('worker', worker, 'takes job', job, 'cost', cost[worker][job])

Example

from functools import lru_cache

cost = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]
n = 3

@lru_cache(maxsize=None)
def assign(mask):
    worker = bin(mask).count('1')
    if worker == n:
        return 0
    best = 10 ** 9
    for job in range(n):
        if not mask & (1 << job):
            best = min(best, cost[worker][job] + assign(mask | (1 << job)))
    return best

print('best assignment cost', assign(0))

dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
m = 4

@lru_cache(maxsize=None)
def tsp(mask, last):
    if mask == (1 << m) - 1:
        return dist[last][0]
    best = 10 ** 9
    for nxt in range(m):
        if not mask & (1 << nxt):
            best = min(best, dist[last][nxt] + tsp(mask | (1 << nxt), nxt))
    return best

print('best tour cost', tsp(1, 0))

Key points

  • A bitmask is an integer whose bits form a tiny set
  • Bit i set means item i is already in the set
  • A state pairs the mask with one last choice or one count
  • Adding an unused item sets one more bit in the mask
  • A table over all masks holds one entry per subset

In this example, the assignment table gives three workers three jobs. The state is the mask of jobs already taken, and the worker index is the popcount of that mask. The tour part visits four cities and returns to the start. Both answers come from tables indexed by masks.

Note

Twelve items give 4096 masks, so small sets fit well

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

In bitmask DP, what does the popcount of a mask often give?