四大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]的定义，我们也可以看出如下递推式：

其中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]);
}