POJ--3311--Hie with the Pie（暴力枚举+floyd）/（状态压缩DP+floyd）

简介

状态压缩入门，先说用暴力枚举的方法做的，再说状态压缩DP，对于刚开始学习状态压缩的同学，两者相互比较学习，可以明显看出两者区别，有利于对状态压缩DP的理解，提前说下，两者耗时是 157Ms和 0Ms 。

题意

一披萨店员送披萨，从披萨店开始送给N个客户会给你一个(N+1)*(N+1)的矩阵，对于矩阵 g[i][j] 表示 i 处到 j 处所耗费的时间，0 代表披萨店，每条路径可以重复走。问：店员从披萨店开始送完所有的披萨再返回店中的最短耗时。注意，出店就拿有 N 个披萨，不必重复返回店里拿；此矩阵不对称，即 g[i][j]!=g[j][i] 。

暴力枚举+floyd的思路：

如果枚举所路过的所有点，因为可以重复走每条线路，所以无法算出深度。应当换个思路再暴力，虽然无法枚举完下一个经过哪个点，但可以枚举完送货的依次顺序，即1~N 的全排列，利用 floyd 预处理，算出从 i 到 j 的最短路存入 g[i][j] ，这样可以忽视 i 到 j 中间路过哪些点；例如，以此送货的路径是 0 1 2 3 4 5 0 (N=5) ，该路径耗时就是 g[0][1]+g[1][2]+g[2][3]+g[3][4]+g[4][5]+g[5][0]，至于中间还重复经过哪些点则不用考虑 ; 全排列用 next_permutation() 函数。代码如下：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int INF=0x7fffffff;
int g[15][15],a[15];
int main()
{
    int N;
    while(scanf("%d",&N)&&N)
    {
        ++N;
        for(int i=0; i<N; ++i)
        {
            for(int j=0; j<N; ++j)
            {
                scanf("%d",&g[i][j]);
            }
        }
        //floyd 算任意两点最短路
        for(int k=0;k<N;++k)
        {
            for(int i=0;i<N;++i)
            {
                for(int j=0;j<N;++j)
                {
                    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
                }
            }
        }

        for(int i=1;i<N;++i)
        {
            a[i]=i;// 1~N 的全排列
        }
        int ans=INF;
        int temp=0;
        do
        {
            int i;
            temp=g[0][a[1]];//从披萨店出发
            for(i=2;i<N;++i)
            {
                temp+=g[a[i-1]][a[i]];
            }
            temp+=g[a[i-1]][0];//回到披萨店
            ans=min(ans,temp);
        }while(next_permutation(a+1,a+N));
        printf("%d
",ans);
    }
return 0;
}

状态压缩DP+floyd的思路

先给一个定义：0 1 1 0 1 0（N=6) 代表第2、3 、5点的披萨都已经送过了（从1开始数）；0 1 1 0 1 0 就是一个状态，它可以由 0 1 0 0 1 0 再把第 3 个点送了之后得到。再把 0 1 二进制转换为十进制数。可以由此设计出一个状态转移方程： dp[i][j]=min(dp[i-(1<<(j-1))][k]+g[k][j])，1<=k<N；dp[i][j]表示状态 i 是把第 j 个点送了之后得到的最短路，而 i-(1<<(j-1)) 是没送 j 之前的状态；g[i][j] 也由 floyd 预处理。代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int INF=0x7fffffff;
int dp[1<<10][15];
int g[15][15];
int N;

int DP(int i,int j)
{
    if(i==(1<<(j-1)))//边界条件，即从披萨店到 j 点
        return g[0][j];
    else if(dp[i][j]!=-1)//记忆化处理
    {
        return dp[i][j];
    }
    else
    {
        int ans=INF,temp=i-(1<<(j-1));//temp保存的就是 i 状态在没送 j 点之前的状态
        for(int k=1; k<N; ++k)
        {
            if(((temp>>(k-1))&1)==1)//判断temp状态可否由 k 达到
            {
                ans=min(ans,DP(temp,k)+g[k][j]);
            }
        }
        dp[i][j]=ans;
        return ans;
    }
}

int main()
{
    while(cin>>N&&N)
    {
        memset(dp,-1,sizeof(dp));
        ++N;
        for(int i=0; i<N; ++i)
        {
            for(int j=0; j<N; ++j)
            {
                cin>>g[i][j];
            }
        }
        //floyd预处理
        for(int k=0; k<N; ++k)
        {
            for(int i=0; i<N; ++i)
            {
                for(int j=0; j<N; ++j)
                {
                    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
                }
            }
        }
        
        int ans=INF,temp=(1<<(N-1))-1;
        for(int i=1;i<N;++i)
        {
            ans=min(ans,DP(temp,i)+g[i][0]);//由 i 点回到披萨店
        }
        cout<<ans<<endl;
    }
    return 0;
}

DP虽然不好理解，但对比时间复杂度，后者N加到20左右都还可以运行，前者13估计就到极限了吧。