Giving Every Worker a Different Job
n workers must be given n jobs, one each, with every job going to exactly one worker.
c[i][j] is what it costs for worker i to do job j.
Print the smallest possible total cost.
3 workers, rows 9 2 7 / 6 4 3 / 5 8 1 -> 9 jobs 2, 3, 1
1 worker, cost 42 -> 42
## Why not greedy
Giving each worker their own cheapest job double-books whatever job is cheapest for several of them. Repairing that by processing workers in some order is where most attempts go, and there is no order that always works: a worker's best choice depends on what the others will be left with.
The 4 x 4 multiplication-table test is built for this. Every naive rule finds 30 and the
answer is 20.
## One index is enough
dp[mask] = the cheapest way to give jobs to the first popcount(mask) workers,
using exactly the jobs in mask
The key observation is that the NUMBER of set bits already says which worker comes next, so there is no second index. Compare this with 581, where the mask says what has been visited but not where you are standing, and a second index is unavoidable.
Recognising when the mask determines the rest of the state is worth more than the recurrence
itself, because it is the difference between 2^n and 2^n * n entries.
dp[0] = 0
i = popcount(mask)
dp[mask | (1<<j)] = min(dp[mask | (1<<j)], dp[mask] + c[i][j]) for j not in mask
The answer is dp[full].
## Counting the bits
popcount is a single instruction on modern processors and every language exposes it:
__builtin_popcount in C and C++, Integer.bitCount in Java, bin(m).count('1') in Python.
Recomputing it by a loop inside the inner body is the usual reason a correct solution is slow.
## Cost
Time O(2^n * n). Space O(2^n).
At n = 18 that is about 5 million steps and a table of 262144 entries.
## Boundaries
One worker takes the only job. A matrix of equal costs answers n times that value, which is
a free check that nothing is being double counted.