2 mjsunrise MJsunrise 于 2014.12.20 15:28 提问

求助运动员最佳匹配问题代码注释的纠正

不明白 for ( i=0; i<=n; i++ ) a[i]=i,表示什么
还有 cc+=p[j][a[j+1]-1]*q[a[j+1]-1][j]; 是怎么计算的

问题描述:羽毛球队有男女运动员各n 人, 给定2个n*n 矩阵P 和Q, 其中P [i][ j]表示男运动员i 和女运动员j 配对组成混合双打时的竞赛优势;Q[i][ j]则是女运动员i 和男运动员j 配对组成混合双打时的竞赛优势。由于技术的配合和心理状态等各种因素的影响, 一般P[i][ j]不一定等于Q[i][ j]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][ j] * Q[i][ j]。设计一个算法,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。
 设计要求:
设计一个算法,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。
 数据输入:
由文件input.txt给出输入数据。第一行有一个正整数n(1≤n≤20)。接下来的2n行,每行n个数。前n行是p,后n行是q。

#include
using namespace std;
int a[10]; //排列编号
int p[10][10]; //男运动员i和女运动员j配对竞赛优势
int q[10][10]; //女运动员i和男运动员j配对竞赛优势
int n; //男女运动员各n人
int bestc=0; //男女搭配优势的最优值,初始值为0
void swap ( int &x,int &y )//交换函数
{
int temp=x;
x=y;
y=temp;
}
void Backtrack ( int t )//递归回溯函数,t为层数(初始值为1)
{
if ( t>n ) //当层数大于n(男女运动员各n人)时

{
int cc=0;
for ( int j=0; j {
cc+=p[j][a[j+1]-1]*q[a[j+1]-1][j]; //计算当前值cc
}
if ( cc>=bestc ) bestc=cc; //若满足 cc>=bestc时,则需更新当前最优值
}
else
{
for ( int i=t; i<=n; i++ ) //否则,按深度优先的策略继续往下搜索
{
swap ( a[i],a[t] ); //交换当前排列编号和最优排列
Backtrack ( t+1 ); //调用回溯函数,继续搜索
swap ( a[i],a[t] ); //直到找到最优值
}
}
}
int main()
{
int i,j; //男运动员i,女运动员j
while ( cin>>n ) //输入男运动员人数或女运动员人数
{
for ( i=0; i<=n; i++ ) a[i]=i;//存放配对男运动员的编号
for ( i=0; i {
for ( j=0; j {
cin>>p[i][j]; //输入男运动员i,女运动员j配对时的比赛优势矩阵。
}
}
for ( i=0; i {
for ( j=0; j {
cin>>q[i][j]; //输入女运动员i,男运动员j配对时的比赛优势矩阵。
}
}
Backtrack ( 1 ); //调用递归回溯函数
cout<<bestc<<endl;//输出最优值
}
return 0;
}


Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!