最优配对问题（集合上的动态规划） —

题目来源：紫书P284

题意：

给出n个点的空间坐标（n为偶数， n<=20），把他们配成n/2对，问：怎样配对才能使点对的距离和最小？

题解：

设dp[s]为：状态为s（s代表着某个子集）时，它的最小距离和。

1.对于一个状态s，首先要计算它减少两个点后的状态的最小距离和，然后当前状态才能从这些状态中转移过来。

2.如何转移：对于状态s，在集合中随便找一个点，枚举集合中的其他点与它配对，取距离和最小的那一对。

3.为什么选定一个点，然后枚举集合中的其他点就可以呢？而两个点都要枚举呢？因为：对于选定的点，它总得要和集合中的其他点配对，那么答案就肯定蕴藏在某一次配对中了。而枚举两个点，实际上是多余的。

实现：

1.递推：自底向上，从最小的子集开始计算，然后大的子集就可以从中转移过来。缺点是点数为奇数的情况也考虑进去了（可以预先判断点数是否为偶，以决定是否需要进入计算），速度慢。

2.记忆化搜索：很好理解，对于状态s，假设它的偶数子集的最小距离和都计算出来了，那么选定某个点，再枚举其他点就可以了。而且避免了奇数个元素的子集的计算。

递推：

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

const int INF = 2e9;

const int maxn = 21;

struct Node{

    double x, y, z;

}dot[maxn];

int n;

double dp[1<<maxn+1];

double dis(Node a, Node b)

{

    return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) + (a.z - b.z)*(a.z - b.z) );

}

void solve()

{

    dp[0] = 0;

    for(int i = 1; i<(1<<n); i++)

        dp[i] = INF;

    for(int s = 1; s < (1 << n); s++)

    {

        int i;

        for(i = 0; i<n; i++)

            if(s&(1<<i)) break;

        for(int j = i+1; j<n; j++)

            if(s&(1<<j))

                dp[s] = min(dp[s], dis(dot[i], dot[j]) + dp[s^(1<<i)^(1<<j)]);

    }

}

int main()

{

    cin >> n;

    for(int i = 0; i < n; i++)

        cin >> dot[i].x >> dot[i].y >> dot[i].z;

    solve();

    cout << dp[(1<<n) - 1] << endl;

}

记忆化搜索：

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

const int INF = 2e9;

const int maxn = 21;

struct Node{

    double x, y, z;

}dot[maxn];

int n;

double dp[1<<maxn];

double dis(Node a, Node b)

{

    return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) + (a.z - b.z)*(a.z - b.z) );

}

double dfs(int s)

{

    if(dp[s] != INF)

        return dp[s];

    int i;

    for(i = 0; i<n; i++)

        if(s&(1<<i)) break;

    for(int j = i+1; j<n; j++)

        if(s&(1<<j))

         dp[s] = min( dp[s], dis(dot[i], dot[j]) + dfs(s^(1<<i)^(1<<j)) );

    return dp[s];

}

int main()

{

    cin >> n;

    for(int i = 0; i < n; i++)

        cin >> dot[i].x >> dot[i].y >> dot[i].z;

    dp[0] = 0;

    for(int i = 1; i < (1<<n); i++)

        dp[i] = INF;

    cout << dfs((1<<n) - 1) << endl;

}

巴特西

最优配对问题（集合上的动态规划） —— 状压DP

最新文章

热门文章