Part of the explanation of compressed dp refers to the blog post Compressed DP Detailed Explanation (Bitwise Operation)
1. What is compressed dp?#
This is a quote.
Compressed dp compresses the state into binary to save space. For example, in a matrix, compressing the state of a row into a binary string. In dp[S][v], S represents the set of vertices that have been visited, and v represents the current vertex. S represents a state (in binary), (11001)~2~ represents that the three vertices {0, 3, 4} have been visited in binary, and (11001)~2~ represents the decimal number 25. So when S is 25, it actually represents that the three vertices {0, 3, 4} have been visited. If there are a total of 5 vertices (numbered 01234), when all vertices have been visited, Sj is (11111)~2~.
2. Common bitwise operations#
Here are some examples of the above operations. For example, for (11001)~2~, which represents that vertices 0, 3, and 4 have been visited, if I want to visit vertex 2 next, I can do the following operations: 1. Check what the third bit is. To extract the kth bit of a binary number x, y = x >>(k-1) & 1, y = (110)~2~ & 1 = 0. 2. Change the third bit to 1, y = x | (1<<(k-1)), y = (11001)~2~ | (100)~2~ = (11101)~2~, so vertex 2 has been visited, added to the set S, and the process is complete. At this point, S is (11101)~2~ = 29.
3. Example Problems#
A-Hie with the Pie#
Problem Description#
Given the time required to travel between all locations (travel time may vary), how to deliver all orders to each location and return to the pizza shop (numbered 0) in the shortest time?
Approach#
First, use the Floyd algorithm to obtain the shortest path matrix. Use S to represent the state, dp[S][i] represents the shortest time required to reach the i-th location. From S, we can know which cities have been reached. S = 1<<N-1 represents the state of all deliveries completed (N bits are all 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) {//S's all states
for(int i = 1; i <= N; ++i) {//all locations to be delivered
if(S & ( 1<<(i-1) )) { //deliver to location i
if(S == ( 1<<(i-1) )) {//if S has not 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 the delivered locations except the current location and check if the 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 Description#
Given N cities and M roads with costs, Mr. Acmer wants to visit all cities and visit each city at most twice. Find the minimum cost required. If such a route cannot be found, output -1.
Approach#
Use ternary compressed dp. Each bit represents whether a city has been visited: 0 means not visited, 1 means visited once, and 2 means visited twice. Here, cnt[i][j] represents the j-th bit of i in ternary from right to left, and three[i] represents the i-th bit weight of ternary, similar to 1<<i in binary. Finally, compare with ans if all cities have been visited and each city has been visited at most twice.
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] represents the maximum value of the i-th bit in ternary, similar to 1<<i in binary
int map[maxn][maxn];
int cnt[maxt][maxn];//cnt[i][j] represents the j-th bit of i in ternary from right to left
int dp[maxt][maxn];//dp[i][j] represents the total cost after going to 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) {//S's all states
bool allvis = true;
for(int i = 1; i <= N; ++i) {//enumerate each city
if(cnt[S][i] == 0) //some cities have not been visited in this state
allvis = false;
if(dp[S][i] == -1) continue;
for(int j = 1; j <= N; ++j) { //enumerate the next city that can be visited
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]) { //total cost to the next city is smaller
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;
}