这道题可以看为排列数的一个典型模块
一、算法实现题：
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
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 }