腾讯云做视频网站,网页主要由三部分组成,wordpress wp_term_taxonomy,网络广告营销的典型案例这道题可以看为排列数的一个典型模块一、算法实现题#xff1a;1、问题描述#xff1a;羽毛球队有男女运动员各n人#xff0c;给定2个nn矩阵P和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势#xff1b;Q[i][j]则是女运动员i和男运动员j配合的女运动…这道题可以看为排列数的一个典型模块一、算法实现题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.txt3 5210 2 32 3 43 4 52 2 23 5 34 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 #include2 using namespacestd;3 intn;4 int p[100][100];5 int q[100][100];6 int x[100];7 int best[100];8 int answer0;9 void swap(int a,int b){10 inttemp;11 tempa;12 ab;13 btemp;14 }15 voidupdate(){16 int sum0;17 for(int i1;in;i){18 sump[i][x[i]]*q[x[i]][i];19 }20 if(sumanswer){21 answersum;22 for(int i1;in;i){23 best[i]x[i];24 }25 }26 }27 void backtrace(intlevel){28 if(leveln){29 update();3031 }32 else{33 for(int ilevel;in;i){34 swap(x[level],x[i]);35 backtrace(level1);36 swap(x[level],x[i]);37 }38 }39 }40 intmain()41 {4243 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 i1;in;i){49 for(int j1;jn;j){50 cin p[i][j];51 }52 }53 for(int i1;in;i){54 for(int j1;jn;j){55 cin q[i][j];56 }57 }58 for(int i1;in;i){59 x[i]i;60 }61 backtrace(1);62 cout answer
