algorithm - 如何根据变量将 1 个集合平衡到多个其他集合？

Question

本质上，我总共有 20 个玩家，他们每个人都有 2 个属性；

{
    "name": "John Doe",
    "goals": 20
}

我想要完成的是将球员列表和他们的目标输入到一个算法中，该算法将球队平均分成 2 支球队，但它基于他们的目标并以尽可能小的差异平衡球队。玩家的数量总是能被 2 整除，所以这不是问题！

例如，假设我们在一个数组/集合中有 4 个（为简洁起见）玩家；

1. “约翰·多伊” - 5个进球
2. “Jane Doe” - 1个进球
3. “詹姆斯·多伊”——3 球
4. “马克·多伊”——7个进球

在完成算法之后，这将导致 2 个单独的数组/集合，如下所示；

|    Team 1     |    Team 2     |
|---------------|---------------|
| John Doe      | Jane Doe      |
| James Doe     | Mark Doe      |
|               |               |
| Avg: 4 Goals  | Avg: 4 Goals  |
|               |               |
| Goal Total: 8 | Goal Total: 8 |

显然，有时两支球队并不完全平等，但理想情况下，我希望在这种情况下尽可能接近。EG 说第 1 队有 8 个进球，第 2 队有 7 个进球。

标签： algorithm

Answer 1

我之前在评论中提到过贪婪的解决方案（在对输入进行排序之后）会起作用。但正如和其他人所指出的@Prune，贪婪的解决方案在这里不起作用，而是需要一个动态编程解决方案。以下是我的实现是C++：

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <sstream>
#include <fstream>

class Pair{
    public:
        int difference;
        std::vector <int> solution;

        Pair(){
            difference = -1;
            solution.clear();
        }

        Pair(int d, std::vector <int> v) : difference(d), solution(v){}

        bool operator < (const Pair &p) const{
            return difference < p.difference;
        }
};

class Player{
    public:
        std::string name;
        int goals;

        Player() = default;
        Player(std::string n, int g) : name(n), goals(g) {}

        friend std::ostream& operator << (std::ostream& out, const Player &player);
};

std::ostream& operator << (std::ostream& out, const Player &player){
    out << "Player Name: " << player.name << " Player Goals: " << player.goals;
    return out;
}

constexpr int MAX_PLAYER = 6;
constexpr int MAX_GOAL = 101;
constexpr int INF = 1e9;

Pair dp[MAX_PLAYER + 5][MAX_GOAL + 5];

Pair partition(std::vector <Player> players, int index, int val, std::vector <int> result, int sum){
    if(index == players.size() || result.size() == (players.size() / 2)){
        int oppostion = sum - val;
        if(result.size() == players.size() / 2) return Pair(std::abs(val - oppostion), result); 
        return Pair(INF, std::vector <int>()); // return a high difference + empty vector
    }

    if(dp[index][val].difference != -1) {
        return dp[index][val];
    }

    Pair ret1 = partition(players, index + 1, val,  result, sum);
    result.push_back(index);
    Pair ret2 = partition(players, index + 1, val + players[index].goals, result, sum);
    //std::cout << " index " << index << " val " << val << "\n";

    return dp[index][val] = (ret1 < ret2 ? ret1 : ret2);
}

std::vector <Player> readInput(std::ifstream &ifs){
    std::vector <Player> players;
    std::string inputLine;
    while(std::getline(ifs, inputLine)){
        std::istringstream iss(inputLine);
        std::string name;
        int goals;
        iss >> name >> goals;
        players.emplace_back(name, goals);
    }
    return players;
}

auto accumulate_func = [](int accumulator, const Player& player){
   return accumulator + player.goals;
};

int main(int argc, char const *argv[])
{
    //freopen("out.txt", "w", stdout);
    std::ifstream ifs("in.txt");
    std::vector <Player> players = readInput(ifs);

    int sumGoals = std::accumulate(players.begin(), players.end(), 0, accumulate_func);

    std::cout << "Total Goals: " << sumGoals << "\n";

    Pair ret = partition(players, 0, 0, std::vector <int> (), sumGoals);
    std::cout << "Optimal goal difference " << ret.difference << '\n';

    std::vector <Player> teamA;
    std::vector <Player> teamB;

    std::vector <int> teamAIndices;

    for(int index : ret.solution){
        teamAIndices.push_back(index);
        teamA.push_back(players[index]);
    }

    for(int i = 0, k = 0 ; i < players.size() ; ++i){
        if(i == teamAIndices[k]){
            // this player has already been considered
            k++;
        } else{
            teamB.push_back(players[i]);
        }
    }


    std::cout << "-----Team A-----\n";
    for(const Player &player : teamA){
        std::cout << player << "\n";
    }

    std::cout << "\n";

    std::cout << "-----Team B-----\n";
    for(const Player &player : teamB){
        std::cout << player << "\n";
    }

    int goalsTeamA = std::accumulate(teamA.begin(), teamA.end(), 0, accumulate_func);
    int goalsTeamB = std::accumulate(teamB.begin(), teamB.end(), 0, accumulate_func);

    std::cout << "\nGoals of Team A: " << goalsTeamA << " Goals of Team B: " << goalsTeamB << "\n";
    std::cout << "Average goals of Team A: " << goalsTeamA / static_cast <double> (teamA.size()) << " Average goals of Team B: " << goalsTeamB / static_cast <double> (teamB.size()) << "\n";

    return 0;
}

输入：

John_Doe 10
Jane_Doe 15
James_Doe 7
Mark_Doe 25
X_Doe 9
Y_Doe 31
Z_Doe 3
A_Doe 1

输出：

Total Goals: 101
Optimal goal difference 1
-----Team A-----
Player Name: John_Doe Player Goals: 10
Player Name: X_Doe Player Goals: 9
Player Name: Y_Doe Player Goals: 31
Player Name: A_Doe Player Goals: 1

-----Team B-----
Player Name: Jane_Doe Player Goals: 15
Player Name: James_Doe Player Goals: 7
Player Name: Mark_Doe Player Goals: 25
Player Name: Z_Doe Player Goals: 3

Goals of Team A: 51 Goals of Team B: 50
Average goals of Team A: 12.75 Average goals of Team B: 12.5

我在球员的名字和姓氏之间加了一个下划线，因为我不想处理输入解析非常多（由空格分隔的可变数量的名称部分......）。您可以将 替换_为空格。

对于帖子中提到的输入，它给出：

Total Goals: 16
Optimal goal difference 0
-----Team A-----
Player Name: John_Doe Player Goals: 5
Player Name: James_Doe Player Goals: 3

-----Team B-----
Player Name: Jane_Doe Player Goals: 1
Player Name: Mark_Doe Player Goals: 7

Goals of Team A: 8 Goals of Team B: 8
Average goals of Team A: 4 Average goals of Team B: 4

评论中给出的输入@Prune：

John_Doe 20
Jane_Doe 12
James_Doe 10
Mark_Doe 8
X_Doe 6
Y_Doe 5
Z_Doe 4
A_Doe 3

输出：

Total Goals: 68
Optimal goal difference 0
-----Team A-----
Player Name: Jane_Doe Player Goals: 12
Player Name: James_Doe Player Goals: 10
Player Name: Mark_Doe Player Goals: 8
Player Name: Z_Doe Player Goals: 4

-----Team B-----
Player Name: John_Doe Player Goals: 20
Player Name: X_Doe Player Goals: 6
Player Name: Y_Doe Player Goals: 5
Player Name: A_Doe Player Goals: 3

Goals of Team A: 34 Goals of Team B: 34
Average goals of Team A: 8.5 Average goals of Team B: 8.5

根据输入更改MAX_PLAYERand 。MAX_GOALS