这几天碰到了状压DP的题，然后学一学，从白书开始学，持续更新中：

//状压DP学习：
旅行商问题：
给定n个顶点组成的带权有向图的距离矩阵d(I,j)(INF代表没有边)，
要求从顶点0出发，经过每个顶点恰好一次后再回到顶点0，
问所经过的边的总权重的最小值是多少？ 
限制条件：
2<=n<=15
0<=d(i,j)<=1000 
样例见白书P191 
假设现在已近访问过的顶点的集合(起点0当做还未访问过的顶点)为S
当前所在的顶点为v
dp[S][v]表示从v出发访问剩余的所有顶点，最终回到顶点0的路径的权重总和的最小值。
由于从v出发移动到任意一个节点 u不属于S ： 
获得状态转移方程：
dp[v][0]=0; 
dp[S][v]=min(dp[S|u][u]+d(v,u) /*u不属于S*/);
//下面的这个dp可以在 O(2^n * n^2) 的时间内完成计算， 
int n;
int d[MAXN];
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/*所有的元素都存在S集合中*/&&v==0)//  && 又回到了原点 
		return dp[S][v]=0;//初始化距离为0 
	int res=INF;//初始化 
	for(int u=0;u<n;++u)//遍历所有的点 
	{
		if((S>>u&1)==0)//第u位没有选择 
			res=min(res,rec(S|1<<u,u)/*将u位置加入集合*/+d[v][u]);//前面的集合加上d[v][u] 
	}
	return dp[S][v]=res;
}

void solve()
{
	clean(dp,-1);//初始化dp 
	cout<<rec(0,0)<<endl;//从0，0开始 
}

int main()
{
    std::ios::sync_with_stdio(false);
    solve();
    
}

//或者用递推的方式写出dp式子：

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)==0)
					dp[S][v]=min(dp[S][v],dp[S|1<<u][u]+d[v][u]);
			}
		}
	}
	cout<<dp[0][0]<<endl;
}

然后是POJ-2686

//POJ-2686 
旅行家出行，共有m个城市，城市之间有道路相连，
从一个城市到另一个城市去需要马车才行，乘坐马车需要使用车票
每一张车票只能使用一次且只能通过一条道路，每张车票能使用不同数量的马 
通过道路所用的时间是：道路长度/马匹的数量 
旅行家共有n张车票，第i张车票上记录马的数量是ti，
求出从a城市到b城市所需要的最短时间，如果无法到达则输出impossinle 

int n,m,a,b;
int t[MAXN];
int d[MAXN][MAXN];
double dp[1<<MAXN][MAXN];

void solve()
{
	for(int i=0;i<1<<MAXN;++i)
		clean(dp[i],dp[i]+m,INF);
	dp[(1<<n)-1][a-1]=0;
	double res=INF;
	for(int S=(1<<n)-1;S>=0;--S)
	{
		res=min(res,dp[S][b-1]);
		for(int v=0;v<m;++v)
		{
			for(int i=0;i<n;++i)
			{
				if(S>>i&1)
				{
					for(int u=0;u<m;++u)
					{
						if(d[v][u]>=0)//存在 
							dp[S&~(1<<i)][u]=min(dp[S&~(1<<i)][u],dp[S][v]+(double)d[v][u]/t[i]);
					}
				}
			}
		}
	}
	if(res=INF)
		cout<<"NO"<<endl;
	else
		cout<<res<<endl;
	
}