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)2 means vertices {0, 3, 4} have been visited. The decimal value of (11001)2 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)2.
II. Common Bit Operations
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;
}
喜欢的话，留下你的评论吧～