四大dp系列--状压dp

状压dp

状态压缩dp，是一种将复杂的状态压缩成二进制数字的算法。

旅行商问题

我们来看一个经典的旅行商问题：

给定一个n个顶点组成的带权有向图的距离矩阵d(i,j)(INF表示没有边)。要求从顶点0出发，经过每个顶点恰好一次后再回到顶点0。问所经过的边的总权重的最小值是多少？（来源于《挑战程序设计竞赛》）。

限制条件：

2<=n<=15

0<=d(i,j)<=1000

所有可能的路线会有 (n-1)! 种结果，因此我们不能够使用暴力的方法求解，那么我们需要用高效的方法来求解。

假如我们对每个顶点编号。我们可以用一个数的二进制来表示走过的集合 S ：

当n=5时，00000表示所有顶点均未走过，00001表示经过编号为0的顶点，10001表示经过第0和第4个顶点。11111表示经过所有的顶点。

这样，我们就能使用2^n次方个数来表示出所有的状态。

定义dp[S][v]：从v出发，访问剩余未访问过的节点所需要的最小花费。特别的，当S=2^n-1，v=0时,dp[S][v]=0。

从dp[S][v]的定义，我们也可以看出如下递推式：

dp[S][v]=min(dp[S∪u][u]+d[v][u]|u∉S)

其中u表示从v出发到达的下一个顶点。 S ∪ { u } 表示现在经过的所有顶点，由于是从 v 到 u ，所以当前的出发点也为u。d[v][u]表示从顶点 v 到顶点 u 的花费。

找出了递推式，我们就可以使用记忆化搜索的方式找出最小花费：

int n;
int d[maxn][maxn];//储存地图信息，初始化为 INF
int dp[1<<maxn][maxn];//记忆化搜索使用的数组
int rec(int S,int v){//当前走过的节点集合 S，出发顶点v
   if(dp[S][v]>=0){
       return dp[S][v];//由于我们使用的是递归的方法，所以如果有解，储存的一定是最优的解
   }
   if(S==(1<<n)-1 && v==0){//访问过所有定点，并且回到最初起点0，那么在这个状态之后的花费一定是0，即不需要再有其他的花费
       return dp[S][v]=0;
   }
   int res=INF;
   for(int u=0;u<n;u++){
       if(!(S>>u&1)){//第u个节点未被访问
           res=min(res,rec(S|1<<u,u)+d[v][u]);//递归 S|1<<u表示走过u之后的节点集合，因为是走到u，所以新的出发点也是u
       }
   }
   return dp[S][v]=res;
}
int solve(){
   memset(dp,-1,sizeof(dp));//-1表示未被访问过
   printf("%d\n",rec(0,0));
}

由于状压dp的特性，我们只能求解n比较小的情况，否则内存就会超限。

思考上述代码后，我们可以发现，每一个比较小的节点集合都是由比较大的节点集合计算出来的。即对于两个集合S( i ) ∈ S( j ) ，有 i <= j 。我们在求S( i )时，需要先求出来S( j )的值。因此，我们也可以用循环的方法求解：

int n;
int d[maxn][maxn];
int dp[1<<maxn][maxn];
void solve(){
   for(int S=0;S<1<<n;S++){
       fill(dp[S],dp[S]+n,INF);
   }
   dp[(1<<n)-1][0]=0;
   for(int S=(1<<n)-2;S>=0;S--){
       for(int v=0;v<n;v++){
           for(int u=0;u<n;u++){
               if(!(S>>u&1)){
                   dp[S][v]=min(dp[S][v],dp[S|1<<u][u]+d[v][u]);
               }
           }
       }
   }
   printf("%d\n",dp[0][0]);
}