算法(六)-运动员最佳配对问题回溯法

问题描述：

算法描述：

代码：

#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;
}