运动员最佳配对问题

2018/12/28 00:12
阅读数 1.5K

 

这道题可以看为排列数的一个典型模块

一、算法实现题:

1、问题描述:

羽毛球队有男女运动员各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]。设计一个算法,计算男女运动员的最佳配对法,使各组男女双方竞赛优势的总和达到最大。

 

2、编程任务:

设计一个算法,对于给定的男女运动员竞赛优势,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。

 

3、数据输入:

由文件input.txt给出输入数据;第一行有1个正整数n(1≤n≤20);接下来的2n行,每行n个数,前n行是P,后n行是Q。

 

4、结果输出:

将计算的男女双方竞赛优势的总和的最大值输出到文件output.txt。

           输入文件示例               输出文件示例

               intput.txt                   output.txt

               3                          52

               10 2 3

               2 3 4

               3 4 5

               2 2 2

               3 5 3

               4 5 1

二、解题思路

1、求问题的解空间

   对于n个男运动员,从第1个开始搭配女运动员:第1个有n种搭配方法,第2个有n-1种搭配方法……第n个有n-(n-1)种搭配方法;根据问题给出的示例:输入n的值为3,表示男女运动员各有3名;

男运动员 1 2 3按顺序搭配女运动员,他们分别对应的女运动员可以是:

女运动员 1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1

所以其解空间是{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)},整个问题可看成是1,2,3的全排列问题,将解空间组织成一棵排列树如下

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 int p[100][100];
 5 int q[100][100];
 6 int x[100];
 7 int best[100];
 8 int answer=0;
 9 void swap(int &a,int &b){
10  int temp;
11  temp=a;
12  a=b;
13  b=temp;
14 }
15 void update(){
16 int sum=0;
17 for(int i=1;i<=n;i++){
18     sum+=p[i][x[i]]*q[x[i]][i];
19     }
20     if(sum>answer){
21         answer=sum;
22         for(int i=1;i<=n;i++){
23             best[i]=x[i];
24         }
25     }
26 }
27 void backtrace(int level){
28    if(level>n){
29       update();
30 
31    }
32    else{
33     for(int i=level;i<=n;i++){
34     swap(x[level],x[i]);
35     backtrace(level+1);
36     swap(x[level],x[i]);
37    }
38    }
39 }
40 int main()
41 {
42 
43     cin >> n;
44     memset(p,0,sizeof(p));
45     memset(q,0,sizeof(q));
46     memset(best,0,sizeof(best));
47     memset(x,0,sizeof(x));
48     for(int i=1;i<=n;i++){
49         for(int j=1;j<=n;j++){
50             cin >> p[i][j];
51         }
52     }
53      for(int i=1;i<=n;i++){
54         for(int j=1;j<=n;j++){
55             cin >> q[i][j];
56         }
57     }
58     for(int i=1;i<=n;i++){
59         x[i]=i;
60     }
61     backtrace(1);
62     cout << answer << endl;
63     for(int i=1;i<=n;i++){
64         cout << best[i]<< " ";
65     }
66     return 0;
67 }

 

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部