问题描述:
算法描述:
代码:
#include <iostream> using namespace std; class Player { public: Player(int n) { this->n = n; man = new int*[n+1]; woman = new int*[n+1]; count = new int*[n+1]; for(int i = 0; i <= n; i++) { man[i] = new int[n+1]; woman[i] = new int[n+1]; count[i] = new int[n+1]; } for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) { man[i][j] = 0; woman[i][j] = 0; count[i][j] = 0; } type = new int[n+1]; } ~Player() { for(int i = 0; i <= n; i++) { delete[] man[i]; delete[] woman[i]; } delete[] man; delete[] woman; delete[] type; } void calcPlayer();//计算出最优值 private: void initPlayer();//输入男女运动员的各参数,并计算机各种组合方式的乘积 void swap(int &, int &);//交换两个数 void backtrack(int);//回溯计算 private: int **man; int **woman; int **count;//男女运动员乘积 int *type;//男女运动员的组合方式 int n;//运动员的个数 int nowBest;//当前最大值 int best;//最大值 }; void Player::initPlayer() { cout<<"请输入P(男运动员*女运动员)的参数:"<<endl; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin>>man[i][j]; cout<<"请输入Q(女运动员*男运动员)的参数:"<<endl; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin>>woman[i][j]; //各个组合方式的乘积 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) count[i][j] = man[i][j] * woman[j][i]; //有多少种组合方式 for(int i = 1; i <= n; i++) type[i] = i; nowBest = 0; best = 0; } void Player::swap(int &x, int &y) { int temp; temp = x; x = y; y = temp; } void Player::backtrack(int level) { if(level > n) { if(nowBest > best) best = nowBest; } else { for(int i = level; i <= n; i++) { swap(type[level], type[i]); nowBest = nowBest + count[level][type[level]]; backtrack(level+1); nowBest = nowBest - count[level][type[level]]; swap(type[i], type[level]); } } } void Player::calcPlayer() { initPlayer(); backtrack(1); cout<<"最佳组队方式为:"<<best<<endl; } int main() { cout<<"请输入有多少组队员:"<<endl; int n;//多少组队员 cin >> n; Player player = Player(n); player.calcPlayer(); system("pause"); return 0; }