Bitmask DP: assigning tasks to people

Why this matters

A team lead has 3 people and 3 tasks. Each person can do each task, but the time it takes depends on the pair. The lead wants one task per person with the smallest total time. This is the assignment problem.

With 3 people there are only 3 factorial (6) ways to hand out the tasks. With 10 people there are 3,628,800 ways, and with 20 people there are about 2.4 times 10 to the 18th. Checking every way is too slow for a large team, but a bitmask method handles about 20 people.

Bitmask DP stores a set of tasks as the bits of one whole number. Each task gets one bit. A bit that is 1 means that task is in the set. The travelling salesman lesson before this one explains the bit operations in detail. This lesson uses the same operations for a different question.

The lesson also asks a second question: which sets of tasks can be handed out at all? Some pairs may be forbidden, so some sets are impossible. Counting the reachable sets shows how much of the table is actually used.

The idea: people in order

Give the people numbers 0, 1, 2, and so on. Process them in that order. Person 0 gets a task first, then person 1, and so on.

Here is the key fact. When person p is about to get a task, exactly p tasks have already been given out. So the set of tasks already given out tells us which person is next. If the set has 2 tasks, the next person is person 2.

The number of bits set to 1 in a mask is its population count. In C++20 this is std::popcount, from the <bit> header. So the next person is std::popcount(static_cast<unsigned>(mask)), since std::popcount only accepts unsigned types. The program does not need a separate counter for people.

The state is:

dp[mask] is the cheapest total cost of giving exactly the tasks in mask to the first popcount(mask) people.

The start is dp[0] = 0. Nobody has a task yet, and the cost is zero.

The step is:

• Let p be popcount(mask), the next person.
• Try each task t that is not in mask.
• Skip the pair if person p cannot do task t.
• Otherwise, the new set is mask | (1 << t), and its cost is dp[mask] + cost[p][t].
• Keep the smallest cost over all ways to reach that new set.

The answer is dp[full], the cost of giving all tasks to all people. Here full is (1 << n) - 1, the mask with every bit set.

Some states can never be reached. For example, if no person can do task 2, then every set that contains task 2 is unreachable. The program stores a large number for those states, meaning "impossible". A state is reachable when its cost is not that large number.

As in the travelling salesman lesson, the processing order is from the smallest mask number to the largest. Adding a task always makes the mask number bigger, so each state is finished before it is used.

Why not give each person their cheapest task

The obvious first idea is greedy. Go through the people in order, and let each person take the cheapest task that is still free. It is quick, but it can be wrong.

Use the first example from below, with the same costs:

           task 0  task 1  task 2
person 0      9       2       7
person 1      6       4       3
person 2      5       8       1

Person 0 takes task 1, which costs 2, the cheapest for that person. Person 1 takes task 2 at cost 3, the cheapest free task. Person 2 is left with task 0 at cost 5. The total is 2 + 3 + 5 = 10.

The best assignment costs 9. Person 0 takes task 1 (cost 2), person 1 takes task 0 (cost 6), and person 2 takes task 2 (cost 1). Person 1 gives up its cheapest task, which costs 3, so that person 2 can have task 2, which costs only 1 for person 2. The greedy rule cannot see that trade, because it decides each person's task without looking at what the later people need.

The table avoids this problem because it keeps the cheapest way to reach every set. For example, dp[{0, 1}] is 8, from person 0 taking task 1 and person 1 taking task 0. Adding person 2 with task 2 at cost 1 gives 9. The final answer is the best of all such paths to the full set.

Worked example by hand

Three people and three tasks. The table shows the cost of each pair:

           task 0  task 1  task 2
person 0      9       2       7
person 1      6       4       3
person 2      5       8       1

Layer 1 means one task has been given out, to person 0:

• dp[{0}] is 9, person 0 does task 0.
• dp[{1}] is 2, person 0 does task 1.
• dp[{2}] is 7, person 0 does task 2.

Layer 2 means two tasks have been given out, to persons 0 and 1:

• dp[{0, 1}] is the best of 9 + 4 = 13 (person 0 task 0, person 1 task 1) and 2 + 6 = 8 (person 0 task 1, person 1 task 0). The best is 8.
• dp[{0, 2}] is the best of 9 + 3 = 12 (person 0 task 0, person 1 task 2) and 7 + 6 = 13 (person 0 task 2, person 1 task 0). The best is 12.
• dp[{1, 2}] is the best of 2 + 3 = 5 (person 0 task 1, person 1 task 2) and 7 + 4 = 11 (person 0 task 2, person 1 task 1). The best is 5.

Layer 3 is the full set. Person 2 takes the last task:

• From dp[{0, 1}] = 8, person 2 takes task 2 at cost 1. Total 9.
• From dp[{0, 2}] = 12, person 2 takes task 1 at cost 8. Total 20.
• From dp[{1, 2}] = 5, person 2 takes task 0 at cost 5. Total 10.

The best total is 9. It comes from person 0 doing task 1 (cost 2), person 1 doing task 0 (cost 6), and person 2 doing task 2 (cost 1). That is 2 + 6 + 1 = 9.

Each layer's costs come only from the layer before it. The program prints only the total cost. Finding which person did which task needs a parent table, as in the travelling salesman lesson.

The program

This program runs three small examples. The first has every pair allowed. The second has some pairs forbidden, marked with -1. The third has a case where no full assignment exists. For each example it prints the minimum cost and how many sets are reachable in each layer.

Save the file as assign.cpp:

#include <bit>
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
 
constexpr int kInf = std::numeric_limits<int>::max();
 
// cost[p][t] is the cost for person p doing task t. A negative value means
// that person cannot do that task.
// Returns dp, where dp[mask] is the cheapest cost of giving exactly the tasks
// in mask to the first popcount(mask) people, or kInf if that is impossible.
std::vector<int> run_dp(const std::vector<std::vector<int>>& cost) {
    const int n = static_cast<int>(cost.size());
    const int full = (1 << n) - 1;
    std::vector<int> dp(static_cast<std::size_t>(full) + 1, kInf);
    dp[0] = 0;
 
    // Adding a task always makes the mask bigger, so ascending order is safe.
    for (int mask = 0; mask <= full; ++mask) {
        if (dp[mask] == kInf) continue;  // unreachable state, nothing to extend
        const int person = std::popcount(static_cast<unsigned>(mask));
        if (person == n) continue;       // everybody already has a task
        for (int task = 0; task < n; ++task) {
            if (mask & (1 << task)) continue;     // task already taken
            if (cost[person][task] < 0) continue; // this pair is not allowed
            const int next = mask | (1 << task);
            dp[next] = std::min(dp[next], dp[mask] + cost[person][task]);
        }
    }
    return dp;
}
 
long long binomial(int n, int k) {
    long long result = 1;
    for (int i = 1; i <= k; ++i) {
        result = result * (n - k + i) / i;
    }
    return result;
}
 
void report(const std::vector<std::vector<int>>& cost) {
    const int n = static_cast<int>(cost.size());
    const int full = (1 << n) - 1;
    const std::vector<int> dp = run_dp(cost);
 
    int reachable = 0;
    std::vector<int> per_layer(n + 1, 0);
    for (int mask = 0; mask <= full; ++mask) {
        if (dp[mask] != kInf) {
            ++reachable;
            ++per_layer[std::popcount(static_cast<unsigned>(mask))];
        }
    }
 
    std::cout << "minimum cost: "
              << (dp[full] == kInf ? -1 : dp[full]) << '\n';
    std::cout << "reachable states: " << reachable << " of " << (full + 1) << '\n';
    for (int k = 0; k <= n; ++k) {
        std::cout << "  people done = " << k << ": " << per_layer[k]
                  << " of " << binomial(n, k) << " masks\n";
    }
}
 
int main() {
    std::cout << "Example 1: 3 people, every pair allowed\n";
    report({
        {9, 2, 7},
        {6, 4, 3},
        {5, 8, 1},
    });
 
    std::cout << "\nExample 2: 4 people, some pairs forbidden (-1)\n";
    report({
        {4, -1, 2, 8},
        {4, 3, -1, -1},
        {-1, 6, 5, 7},
        {3, -1, -1, 9},
    });
 
    std::cout << "\nExample 3: two people can only do task 0\n";
    report({
        {1, -1, -1},
        {2, -1, -1},
        {3, 6, 7},
    });
}

Compile and run it:

g++ -std=c++20 -Wall -o assign assign.cpp
./assign

The compile step prints no warnings. The run prints:

Example 1: 3 people, every pair allowed
minimum cost: 9
reachable states: 8 of 8
  people done = 0: 1 of 1 masks
  people done = 1: 3 of 3 masks
  people done = 2: 3 of 3 masks
  people done = 3: 1 of 1 masks
 
Example 2: 4 people, some pairs forbidden (-1)
minimum cost: 15
reachable states: 14 of 16
  people done = 0: 1 of 1 masks
  people done = 1: 3 of 4 masks
  people done = 2: 5 of 6 masks
  people done = 3: 4 of 4 masks
  people done = 4: 1 of 1 masks
 
Example 3: two people can only do task 0
minimum cost: -1
reachable states: 2 of 8
  people done = 0: 1 of 1 masks
  people done = 1: 1 of 3 masks
  people done = 2: 0 of 3 masks
  people done = 3: 0 of 1 masks

Example 1 gives 9, the same as the hand calculation.

Reading the code

The main work happens in run_dp. Here is what each part does:

• dp has one entry for each mask, so dp[mask] is the cost for that set. It starts with every entry set to kInf and dp[0] set to 0.
• The loop runs over masks from smallest to largest. Adding a task always makes the mask bigger, so when the loop reaches a mask, its cost is final.
• std::popcount counts the tasks already given out. That count is the person who is next.
• The check if (person == n) continue; stops the loop from reading cost[n], which does not exist, for the full set.
• The two continue lines inside the task loop skip tasks already taken and pairs that are forbidden.
• std::min keeps the cheaper of the old value and the new one. The new value is built from dp[mask], which is never kInf at this point.

The function returns the whole table, not only dp[full]. The report function needs every entry to count reachable sets.

Reading the reachable counts

The layer for k people has one mask for each way to choose k tasks out of n. That count is the binomial coefficient, written C(n, k). For 3 tasks it is 1, 3, 3, 1. The program prints this as "of 1 masks", "of 3 masks" and so on.

If every pair is allowed, every mask is reachable and the counts match the binomial coefficients. The total number of reachable states is 2^n, which is 8 for 3 people.

Example 2 has forbidden pairs, so some masks are missing. Look at the layer for 1 person. Person 0 cannot do task 1 (the -1 in row 0, column 1). So the mask {1} is unreachable, which gives 3 of 4. In the layer for 2 people, the mask {2, 3} is unreachable. Person 0 can do task 2 or 3, but person 1 can only do tasks 0 and 1. So person 1 cannot take task 2 or 3 after person 0 takes the other one. That gives 5 of 6.

Example 3 shows the impossible case. Persons 0 and 1 can both only do task 0. The first person takes task 0, and the second person has no other task to take. So the answer is -1, which the program uses to mean "no full assignment exists". Only 2 of the 8 masks are reachable: the empty set and {0}.

What the counts answer

The last layer has one mask, the full set. It is reachable exactly when every person can get a task, which is the same as dp[full] not being kInf. So the last layer answers a yes or no question: can the whole team be covered? Example 3 shows 0 of 1 there, so the answer is no.

The earlier layers answer a smaller question. How many different sets of k tasks can the first k people be given? A low count in layer 2 means many sets of two tasks cannot be handed to the first two people. A manager who sees that knows where the restriction is, before any cost is compared.

Checking the example 2 answer by hand

The minimum cost for example 2 is 15. One assignment that reaches it is person 0 doing task 2 (cost 2), person 1 doing task 1 (cost 3), person 2 doing task 3 (cost 7), and person 3 doing task 0 (cost 3). That is 2 + 3 + 7 + 3 = 15.

How much work the table takes

The table has one entry for each mask, so it has 2^n entries. Each entry tries up to n tasks. The work is at most 2^n * n.

For 20 people, the table has 2^20 entries, which is 1,048,576. Each entry stores one int (4 bytes), so the table is about 4 MB. The work is at most 20 million steps, which is far less than for the travelling salesman table, because this table has no end-city dimension.

Common mistakes

Forgetting to skip forbidden pairs

If the check if (cost[person][task] < 0) continue; is removed, the program treats -1 as a real cost. Then a forbidden pair can make the total look cheaper. Running the program without that line gives this output for the examples:

Example 2: 4 people, some pairs forbidden (-1)
minimum cost: -4
reachable states: 16 of 16
...
Example 3: two people can only do task 0
minimum cost: 1

The total is -4, which is impossible for real costs, and all 16 sets look reachable. The forbidden pairs have turned into free or negative costs. The third example prints 1 instead of -1, so it wrongly claims a full assignment exists.

Adding to an impossible state

The table stores kInf for unreachable masks. Adding a cost to that value overflows. The program skips every state whose cost equals kInf, with the line if (dp[mask] == kInf) continue;. Without that line, the addition overflows. Signed overflow is undefined behaviour in C++. The compiler's undefined behaviour sanitizer reports it, for example:

runtime error: signed integer overflow: 2147483647 + 4 cannot be represented in type 'int'

The fix is to skip unreachable states before adding to them.

Using the wrong index for the person

A common mistake is to use the mask itself as the person number. Person number 5 does not exist when there are 3 people, so cost[mask][task] reads past the end of the vector. The correct person is std::popcount(mask), which is the number of tasks already given out. Reading past the end of a vector is undefined behaviour, so the program may print a wrong answer or crash.

Printing -1 as a cost

The value -1 is used in two places: as "forbidden" in the cost table and as "impossible" in the printed answer. These are different things. The printed answer is -1 only because report converts kInf to -1 on output. Do not add -1 to a real total, and do not compare a real total with the printed value.

Expecting every mask to be reachable

Many beginners expect the table to be full. It is only full when every pair is allowed. A program that loops over all masks and assumes each one has a value must check dp[mask] != kInf first, as the report function does.

Practice

Each exercise is followed by its answer.

Exercise 1

In example 1 of the program, change the cost of person 1 doing task 0 to a forbidden pair. What is the minimum cost now?

Show the answer

The minimum is 10. The allowed assignments are: person 0 task 0 with person 1 task 1 and person 2 task 2, which costs 9 + 4 + 1 = 14; person 0 task 0 with person 1 task 2 and person 2 task 1, which costs 9 + 3 + 8 = 20; person 0 task 1 with person 1 task 2 and person 2 task 0, which costs 2 + 3 + 5 = 10; person 0 task 2 with person 1 task 1 and person 2 task 0, which costs 7 + 4 + 5 = 16. The smallest is 10.

Exercise 2

For 2 people and 2 tasks, with every pair allowed, the cost table is {{1, 2}, {3, 4}}. What is the minimum cost?

Show the answer

The minimum is 5. Person 0 doing task 0 (cost 1) and person 1 doing task 1 (cost 4) gives 5. Person 0 doing task 1 (cost 2) and person 1 doing task 0 (cost 3) also gives 5.

Exercise 3

With 5 people and every pair allowed, how many masks are in the layer for exactly 2 people done? How many reachable states are there in total?

Show the answer

The layer has C(5, 2) = 10 masks. Every mask is reachable when all pairs are allowed, so the total is 2^5 = 32 reachable states.

Exercise 4

Why does the program check dp[mask] == kInf before it uses dp[mask]?

Show the answer

An unreachable mask holds kInf, the largest int. Adding a cost to it would overflow, which is undefined behaviour. Skipping it also avoids extending a state that does not exist.

Exercise 5

For 20 people, how many masks does the table have, and how many steps does the program take at most?

Show the answer

The table has 2^20, which is 1,048,576 masks. Each mask tries at most 20 tasks, so the program takes at most 20 times 1,048,576, which is 20,971,520 steps.

Summary

• The next person to be given a task is the number of tasks already given out, which is std::popcount(mask).
• dp[mask] is the cheapest cost of giving the tasks in mask to the first people, and the answer is dp[full].
• A forbidden pair must be skipped, not added as a cost.
• Unreachable states hold a large value, and the program must skip them before adding to them.
• Counting reachable masks per layer shows which sets of tasks can actually be handed out.