补充意见 英文:回溯法求解 运动员最佳配对问题
回溯法求解 运动员最佳配对问题
做IT就要做精英,至少4000/月吧?JAVAV工程师权威认证
[上海央邦]学一送一,超值! 【安博亚威】CCIE考试通过率第一!
定向委培RHCA,通过考试年薪10W
Windows高级工程师的培训地
#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; }