progress

~/problems / Advanced DP / Bitmask DP

Cheapest one-to-one job assignment

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy basics ~10 min

n workers, n jobs; cost[i][j] is worker i's price for job j. Each worker gets exactly one job and each job one worker.

Implement min_assignment(cost: list[list[int]]) -> int: the smallest total (0 when n = 0).

min_assignment([[9, 2],
                [3, 8]])      # 5    worker 0 -> job 1 (2), worker 1 -> job 0 (3)

min_assignment([[4, 1, 3],
                [2, 0, 5],
                [3, 2, 2]])   # 5    0 -> job 1, 1 -> job 0, 2 -> job 2: 1 + 2 + 2

0 <= n <= 14, costs 0..1000.

⭐ Bonus: trying all n! orders passes for small n; a speed test with 14 workers earns a star with a table over subsets of jobs (2^14 = 16384 entries, O(2^n · n)).

Show hint

best[mask] is the cheapest way to give the jobs in mask to workers 0 .. popcount(mask) - 1; the next worker i = popcount(mask) taking free job j leads to best[mask | 1 << j].

Topic: Bitmask DP. dp[mask][last] over subsets (n <= ~20): TSP, assignment.

0:00
Ctrl ' run · Ctrl ↵ submit
esc