九乡新闻网补充意见 英文:回溯法求解 运动员最佳配对问题
来源：百度文库 编辑：九乡新闻网 时间：2024/04/28 12:41:23
回溯法求解 运动员最佳配对问题
做IT就要做精英,至少4000/月吧?JAVAV工程师权威认证
[上海央邦]学一送一,超值! 【安博亚威】CCIE考试通过率第一！
定向委培RHCA,通过考试年薪10W
Windows高级工程师的培训地
中国IT实验室收集整理 
佚名 
2008-12-16 
保存本文 
推荐给好友 
收藏本页 欢迎进入C/C++编程社区论坛，与200万技术人员互动交流 >>进入 运动员最佳配问题，羽毛球队有男女运动员各N人给定两个N *N矩阵P和Q. P[I][J]是男运动员I和女运动员J配对组成混合双打的竞赛优势；Q[I][J]是女运动员I 和男运动员J配合的竞赛优势。由于配合和心理状态等各种因素影响，P[I][J]不一定等于Q[J][I].设计一个算法计算男女运动员最佳配对法，使各组男女双方竞赛优势乘积的总和达到最大。 #include "stdafx.h"
#include
#include
#include
#include
using namespace std;
vector
vector
vector
class Queen
{
friend int PairUp(int);
private:
bool Place(int k);
void Backtrack(int k);
int n;
int sum;
vector
public:
Queen(int m,int c,int b)
{
x.resize(m+1);
Re.resize(m+1);
n = c;
sum = b;
}
~Queen() { }
};
bool Queen::Place(int k)
{
for(int j=1;j if(x[j]==x[k]) //不同男运动员和同一个女运动员配对 return false; return true; } void Queen::Backtrack(int t) { if(t>n) { int temp=0; //第次还原为进行下次的累加 for(int i=1;i<=n;i++) { temp += (P[i][x[i]]) * (Q[x[i]][i]); //累加，得到一个可行解 } if(sum<=temp) //记录最大可行解 { sum=temp; copy(x.begin(),x.end(),Re.begin()); } } else for(int i=t;i<=n;i++) { swap(x[t],x[i]); if(Place(t)) Backtrack(t+1); swap(x[t],x[i]); } } int PairUp(int n) { Queen X(n,n,0); vector for(int i=0;i<=n;i++) p.push_back(i); copy(p.begin(),p.end(),X.x.begin()); X.Backtrack(1); return X.sum; } int _tmain(int argc,_TCHAR* argv[]) { ifstream fin("input.txt"); ofstream fout("output.txt"); int n,i,j,temp; vector vector fin>>n; r.push_back(0); P.push_back(r); t.push_back(0); Q.push_back(t); cout<<"从文件input.txt中获得数据...."< for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { fin>>temp; r.push_back(temp); } P.push_back(r); for(vector { vr = r.erase(vr); } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { fin>>temp; t.push_back(temp); } Q.push_back(t); for(vector { vt = t.erase(vt); } } cout<<"结果为："< cout<<"男运动员"<<" & "<<"女运动员"< for(i=1;i<=n;i++) { cout< } fout< return 0; }