将n个玩家分成m个团队，以最小化Java中的团队差异

Question

我遇到了一个问题，我需要SO聪明人的帮助。我想把n名球员分成m支球队。每个玩家都有不同的游戏能力。能力由正整数或负整数表示。一个团队的总能力只是分配给该团队的人员的能力得分的总和。

我的目标是找出总能力最高的球队和总能力最低的球队之间可能存在的最小差异。限制条件是每个球员必须被安排在一个团队中，每个团队必须至少有一名成员。

例如，如果我有以下能力的球员：[1，2，3，4，5，6，7]，并想组建三支球队。因此，总能力最大的团队和总能力最小的团队之间的最小可能差为1。一种可能的解决方案是：

第1组：1+3+6=10

团队2:2+7=9

团队3:4+5=9

我试图通过使用以下策略来划分玩家：

1.分类能力

2.每次将剩余的能力最高的玩家分配到能力最低的组中，直到没有玩家为止

这种策略可以解决一些问题。这是我迄今为止的代码：

public int minDifference(int numTeams, int[] abilities) {
        ArrayList<ArrayList<Integer>> teams = new ArrayList<ArrayList<Integer>>();
        int[] teamSum = new int[numTeams];
        for(int i = 0; i < numTeams; i++){
            teams.add(new ArrayList<Integer>());
            teamSum[i] = 0;
        }
        Arrays.sort(abilities);
        for(int i = abilities.length - 1; i >= 0;  i--){
            int minSum = teamSum[0];
            int minNum = 0;
            for(int j = 1; j < numTeams; j++){
                if(teamSum[j] < minSum){
                    minSum = teamSum[j];
                    minNum = j;
                }
            }
            teams.get(minNum).add(abilities[i]);
            teamSum[minNum] += abilities[i];
        }
        Arrays.sort(teamSum);
        System.out.println(teamSum[numTeams - 1] - teamSum[0]);
        return teamSum[numTeams - 1] - teamSum[0];
    }

现在我被卡住了。我的想法是比较两个团队。说A和B。球员汤姆来自A，杰瑞来自B。如果A-B=10，汤姆-杰瑞=3；然后交换汤姆和杰瑞。所以A-B=4现在继续这样做。但似乎有太多的比较（因为你还需要计算两支球队球员之间的差异），我不知道什么时候该停下来（意味着我怎么知道这是最小的）。

Answer 1

我很确定这是一个NP问题，因为我们是否可以将球员分成两个没有差异的团队的决定是属于NPC的子集和问题。这个问题的任何多项式时间解决方案都是不正确的（或者你可以说NP=P），所以不要浪费时间思考多项式解决方案，只需尝试完全搜索（我的意思是尝试所有m^n可能的解决方案…），如果你认为它太慢，你可以尝试启发式搜索。

Answer 2

我是这么想的。你可以把所有的能力加起来，然后除以团队的数量，然后试着找出总能力尽可能接近这个数字的团队。