Assignment Problem (Bitmask DP)

Difficulty: Hard · Topic: Dynamic programming

Given an n × n matrix cost where cost[i][j] is the cost of giving task j to worker i, assign each worker a distinct task to minimize total cost.

Use bitmask DP: dp[mask] = the min cost to assign the first popcount(mask) workers, where mask is the set of tasks already used. Worker i = popcount(mask) tries each unused task j.

Examples

min_assignment_cost([[9,11,14],[6,15,13],[12,13,6]])
→ 23

w0→t1, w1→t0, w2→t2 = 11+6+6.

min_assignment_cost([[1,2],[3,4]])
→ 5

Target complexity: time O(2ⁿ · n), space O(2ⁿ)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.