This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

The bitmask explanation section references blog post Bitmask DP Detailed Explanation (Bit Operations)

I. What is Bitmask DP?

This is a quote

Bitmask DP compresses states into binary representation for storage. For example, in a matrix, a row's state is compressed into a binary string. In dp[S][v], S can represent the set of already-visited vertices, and v represents the current vertex. S represents a state (in binary). (11001)₂ means vertices {0, 3, 4} have been visited. The decimal value of (11001)₂ is 25, so when S is 25, it means vertices {0, 3, 4} have been visited. If there are 5 vertices in total (labeled 0, 1, 2, 3, 4), then when all vertices are visited, S would be (11111)₂.

II. Common Bit Operations

Here are some examples of the operations above. Using (11001)₂ as mentioned above, which represents having visited vertices 0, 3, and 4. If we next want to visit vertex 2, we can perform the following operations: 1. What is the 3rd bit? Use "extract the k-th bit of binary number x": y = x >> (k-1) & 1, y = (110)₂ & 1 = 0. 2. Set the 3rd bit to 1: y = x | (1<<(k-1)), y = (11001)₂ | (100)₂ = (11101)₂. So after visiting vertex 2 and adding it to set S, S becomes (11101)₂ = 29.

III. Example Problems

A - Hie with the Pie

Problem Statement

Given the travel times between all locations (which may differ in each direction), find the minimum time to deliver orders to all locations and return to the pizza shop (labeled 0).

Approach

First use the Floyd algorithm to get the shortest path matrix. Use S to represent the state. dp[S][i] represents the minimum time to reach location i. From S, we can determine which cities have been delivered to. S = 1<<N-1 represents the state where all deliveries are complete (all N bits are 1).

Code

// A-Hie with the Pie
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 12;
const int inf  = 0x3f3f3f;
int N,S,ans;
int dis[maxn][maxn];
int dp[1<<maxn][maxn];
void Floyd() {
    for(int k = 0; k <= N; ++k) {
        for(int i = 0; i <= N; ++i) {
            for(int j = 0; j <= N; ++j) {
                if(dis[i][j] > dis[i][k] + dis[k][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}
int main(){
    while(scanf("%d", &N) && N) {
        for(int i = 0; i <= N; ++i) {
            for(int j = 0; j <= N; ++j) {
                scanf("%d", &dis[i][j]);
            }
        }
        Floyd();
        for(int S = 0; S < (1<<N); ++S) {//All states of S
            for(int i = 1; i <= N; ++i) {//All delivery locations
                if(S & ( 1<<(i-1) )) {  //Need to deliver to location i
                    if(S == ( 1<<(i-1) )) {//If S hasn't delivered to any location yet
                        dp[S][i] = dis[0][i];
                        break;
                    } else {
                        dp[S][i] = inf;
                        for(int j = 1; j <= N; ++j) {
                            if(j == i) continue;
                            //Enumerate already-delivered locations other than the current one, check if time is shorter
                            if(S&( 1<<(j-1) )) {
                                dp[S][i] = min(dp[S][i],dp[S^(1<<(i-1))][j] + dis[j][i]);
                            }


                        }
                    }
                }
            }
        }
        ans = inf;
        for(int i = 1; i <= N; ++i) {
            ans = min(ans, dp[(1<<N)-1][i] + dis[i][0]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

B - Travelling

Problem Statement

Given N cities and M road costs, Mr. Acmer wants to visit all cities with each city visited at most twice. Find the minimum cost, or output -1 if no such route exists.

Approach

Ternary bitmask DP. Each digit represents: 0 = not visited, 1 = visited once, 2 = visited twice. We use cnt[i][j] to represent the j-th digit (from right) of i in base 3, and three[i] represents the weight of the i-th ternary digit, similar to 1<<i in binary. Finally, if all cities are visited and none is visited more than twice, compare with ans.

Code

// B - Travelling
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 12;
const int maxt = 59049;
const int inf  = 0x3f3f3f;
int N,M,S,ans;
int three[maxn];//three[i] is the max value of the i-th ternary digit, similar to 1<<i in binary
int map[maxn][maxn];
int cnt[maxt][maxn];//cnt[i][j] represents the j-th digit (from right) of i in base 3
int dp[maxt][maxn];//dp[i][j] represents the total cost after visiting city j in state i
void init() {
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            map[i][j] = inf;
        }
        map[i][i] = 0;
    }
}
int main(){
    int x = 3;
    three[0] = 0;
    three[1] = 1;
    for(int i = 2; i < maxn; ++i) {
        three[i] = x;
        x *= 3;
    }
    for(int i = 0; i < three[maxn-1]; ++i) {
        int now = i;
        for(int j = 1; j <= 10 && now; ++j) {
            cnt[i][j] = now % 3;
            now /= 3;
        }
    }
    while(~scanf("%d %d", &N, &M)) {
        init();
        for(int i = 1; i <= M; ++i) {
            int u,v,w;
            scanf("%d %d %d", &u, &v, &w);
            if(w < map[u][v]) {
                map[u][v] = map[v][u] = w;
            }
        }
        for(int i = 1; i <= N; ++i) {
            dp[three[i]][i] = 0;
        }
        int ans = inf;
        for(int S = 0; S < three[maxn-1]; ++S) {//All states of S
            bool allvis = true;
            for(int i = 1; i <= N; ++i) {//Enumerate each city
                if(cnt[S][i] == 0)   //This city hasn't been visited in this state
                    allvis = false;
                if(dp[S][i] == -1) continue;
                for(int j = 1; j <= N; ++j) {   //Enumerate the next city to visit
                    if(i == j || map[i][j] == inf || cnt[S][j] >= 2)
                        continue;
                    int nS = S+three[j];//Next state
                    if(dp[nS][j] == -1 || dp[S][i] + map[i][j] < dp[nS][j]) { //Lower total cost for the next city
                        dp[nS][j] = dp[S][i] + map[i][j];
                    }
                }
            }
            if(allvis) {
                for(int i = 1; i <= N; ++i) {
                    if(dp[S][i] != -1) {
                        ans = min(ans, dp[S][i]);
                    }
                }
            }
        }
        if(ans == inf) printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}