动态规划_复杂状态DP_动态规划 dp

【最优配对问题】

空间里有n个点P₀, P₁, …, P_n-1，你的任务是把它们配成n/2对（n是偶数），使得每个点恰好在一个点对中。所有点对中两点的距离之和应尽量小。n≤20，|xi|,|yi|,|zi|≤10000。

• 状态压缩
• d(i,S) = min{ |Pi Pj| + d(i-1, S-{i}-{j})|j∈S }
  【代码】

 for(int i=0;i<n;i++)
    {
        for(int s=0;s<(1<<(i+1));s++)
        {
            if(s==0) d[i][s]=0;
            else d[i][s]=INF;
            if((s & (1<<i)))
            {
                for(int j=i-1;j>=0;j--)
                if((s & (1<<j)))
                    d[i][s]=min(d[i][s],
                        dis(node[i],node[j])+d[i-1][s^(1<<i)^(1<<j)]);
            }
            else if(i!=0)
            {
                d[i][s]=d[i-1][s];
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

【优化（未测试）】

 for(int i=0;i<n;i++)
    {
        for(int s=(1<<i); s<(1<<(i+1)); s++)
        {
            if(s==0) d[s]=0;
            for(int j=i-1;j>=0;j--)
                if((s & (1<<j)))
                    d[s] = min( d[s],
                      dis(node[i],node[j])+d[s^(1<<i)^(1<<j)]); 
        }
    }
1
2
3
4
5
6
7
8
9
10
11

【货郎担问题（TSP）】

有n个城市，用0，1，2，…，n-1表示，城i，j之间的距离为d_ij，有一个货郎从某城市出发到其他城市一次且仅一次，最后回到该城市，怎样选择行走路线使总路程最短？
【分析】
- 看似无起点，但只需要设初始点为任意一点（如0点）点即可。
- d(i, S) = min{ d(j, S-{j}) + dist(i, j) | j∈S }

【图的色数】

给一个无向图G，把图中的节点染成尽量少的颜色，使得相邻节点颜色不同。
【分析】
设d(S)表示把结点S染色，所需要的颜色数的最小值，则d(S) = min{ d(S-S’) | S’∈ S }。其中S’为独立集。
复杂对为：sum{C(n,k)2^k} = 3^k（二次项定理）
【代码】

d[0] = 0;
for(int S=1; S<(1<<n); i++)
{
    d[S] = INF;
    for(int S0=S; S0; S0=(S0-1)&S)
    {
        if(no_edge_inside(SO) d[S] = min(d[S], d[S-S0]+1);
    }
}
1
2
3
4
5
6
7
8
9