运动员最佳匹配问题 | 回溯：N排列（最大剪枝）

墨蓝 2023-03-13 06:14 28阅读 0赞

> ## 运动员最佳配对问题 ##
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>成绩</td> 
>    <td>10</td> 
>    <td>开启时间</td> 
>    <td>2020年04月7日 星期二 08:55</td> 
>   </tr> 
>   <tr> 
>    <td>折扣</td> 
>    <td>0.8</td> 
>    <td>折扣时间</td> 
>    <td>2020年05月30日 星期六 23:55</td> 
>   </tr> 
>   <tr> 
>    <td>允许迟交</td> 
>    <td>否</td> 
>    <td>关闭时间</td> 
>    <td>2020年05月30日 星期六 23:55</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> 羽毛球队有男女运动员各n人. 给定2个n\*n矩阵P和Q. P\[i\]\[j\]是男运动员i与女运动员j配混合双打的男运动员竞赛优势; Q\[i\]\[j\]是女运动员i与男运动员j配混合双打的女运动员竞赛优势. 由于技术配合和心理状态等各种因素影响, P\[i\]\[j\]不一定等于Q\[j\]\[i\]. 男运动员i和女运动员j配对的竞赛优势是P\[i\]\[j\]\*Q\[j\]\[i\]. 设计一个算法, 计算男女运动员最佳配对法, 使得各组男女双方竞赛优势的总和达到最大.
> 
> 数据输入:第1行有一个正整数n(1<=n<=12), 接下来2n行是P和Q
> 
> 结果输出:最佳配对的各组男女双方竞赛优势总和 
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>&nbsp;</th> 
>    <th>测试输入</th> 
>    <th>期待的输出</th> 
>    <th>时间限制</th> 
>    <th>内存限制</th> 
>    <th>额外进程</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>测试用例 1</td> 
>    <td>&nbsp; 
>     <ol> 
>      <li>3↵</li> 
>      <li>10&nbsp;2&nbsp;3↵</li> 
>      <li>2&nbsp;3&nbsp;4↵</li> 
>      <li>3&nbsp;4&nbsp;5↵</li> 
>      <li>2&nbsp;2&nbsp;2↵</li> 
>      <li>3&nbsp;5&nbsp;3↵</li> 
>      <li>4&nbsp;5&nbsp;1↵</li> 
>     </ol></td> 
>    <td>&nbsp; 
>     <ol> 
>      <li>52↵</li> 
>     </ol></td> 
>    <td>1秒</td> 
>    <td>64M</td> 
>    <td>0</td> 
>   </tr> 
>  </tbody> 
> </table>

--------------------

### 一、回溯的思路 ###

此题最先想到就是暴力枚举，但是合理地暴力枚举我们应该采用回溯法，很明显这里是一个 **N排列 的回溯模型**。

首先将第 i 位男运动员与第 j 位女运动员的优势计算到**二维数组 pq\[ i \]\[ j \]** 中，然后再在这个二维数组选 n 个组合（组合即对应每个点(i , j)），要求 n 个点不可同行或同列，将 n 个这样子符合条件的点求和，记录最大值。

第 i 层回溯对应第 i 位男运动员，该层回溯中应该选取一位没有被选择过的女运动员。为了记录女运动员是否被选择过，我们创建**数组 vis\[ i \]** 来记录，依次累加每一层的优势。当 i > n 时即为回溯的终点，此时更新最大的优势和。

--------------------

### 二、最大问题的剪枝操作 ###

最大问题的剪枝操作稍微比最小问题复杂一点，我们需要预先计算好**数组 pre\[ i \]**：1~i 的男运动员匹配的最大情况（其实就是max：pq\[ i \]\[ j \]）。注意：这个最大的匹配其实是可以让女运动员重复的，因为只是为了贪心地选取最大，为了最后剪枝方便即可。

/* 贪心获取 1~i 男运动员匹配的最大情况：pre[i]
         * 注意：选择可以不合理（女运动员被重复选择），但是只是为了剪枝
         *      只要保证每次是贪心地选取，结果肯定比合理的情况更大 */
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                pre[i] = max(pre[i], pq[i][j]);
            pre[i] += pre[i - 1];
        }

那么在第 i 层回溯中，前 1 ~ i-1 个男运动员是已经安排好的，后面 i ~ n 个男运动员的安排优势不可能超过 pre\[ n \] - pre\[i -1\]！故我们可以通过这一个特点对它进行剪枝：若当前优势加上 pre\[ n \] - pre\[i -1\] 都不可以超过已经记录的最大值，那么就没有必要继续沿着这条线路搜下去了。

--------------------

### 三、代码实现 ###

#include <cstdio>
    #include <algorithm>
    
    #define MAXN 13
    using namespace std;
    
    int n;
    int p[MAXN][MAXN], q[MAXN][MAXN], pq[MAXN][MAXN];
    int pre[MAXN] = {0}; // 0~i 男运动员匹配的最大情况
    bool vis[MAXN] = {false};  //记录女运动员是否被访问过
    int score = 0, best_score = 0;  //记录当前优势 与 当前最大优势
    
    void backtrack(int i) {
        /* 回溯的终点 */
        if (i > n) {
            best_score = max(best_score, score);  //更新最大优势
            return;
        }
    
        /* 剪枝操作：就算后面都不合理贪心选择都不能超过 */
        if (score + pre[n] - pre[i - 1] < best_score)
            return;
    
        /* 在n个女运动员中选择 */
        for (int j = 1; j <= n; j++) {
            if (vis[j])   //女运动员已经被选择
                continue;
    
            vis[j] = true;
            score += pq[i][j];
            backtrack(i + 1);
    
            vis[j] = false;
            score -= pq[i][j];
        }
    }
    
    int main() {
        scanf("%d", &n);
    
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &p[i][j]);
    
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &q[i][j]);
    
        /* 计算得到总表 */
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                pq[i][j] = p[i][j] * q[j][i];
            
        /* 贪心获取 0~i 男运动员匹配的最大情况：pre[i]
         * 注意：选择可以不合理（女运动员被重复选择），但是只是为了剪枝
         *      只要保证每次是贪心地选取，结果肯定比合理的情况更大 */
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                pre[i] = max(pre[i], pq[i][j]);
            pre[i] += pre[i - 1];
        }
        backtrack(1);
        printf("%d\n", best_score);
    }