私は問題に行き詰まっており、SO の明るい頭脳からの助けが必要です。n 人のプレイヤーを m のチームに分けたい。各プレイヤーは異なるゲーム能力を持っています。能力は正または負の整数で表されます。チームの合計能力は、そのチームに割り当てられた人々の能力スコアの合計です。
私の目標は、合計能力が最大のチームと合計能力が最小のチームとの間の最小の差を見つけることです。制約は、各プレーヤーをチームに配置する必要があり、すべてのチームに少なくとも 1 人のメンバーが必要です。
たとえば、[1、2、3、4、5、6、7] の能力を持つプレーヤーがいて、3 つのチームを編成したいとします。したがって、合計能力が最大のチームと合計能力が最小のチームの最小の差は 1 です。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];
}
今、私は立ち往生しています。私の考えは、2 つのチームを比較することです。A と B を言います。プレーヤー A のトムと B のジェリーです。A - B = 10 で、トム - ジェリー = 3 の場合。次にトムとジェリーを入れ替えます。つまり、A - B = 4 です。そして、これを続けてください。しかし、比較が多すぎるようで (2 つのチームの選手間の差も計算する必要があるため)、停止するタイミングがわかりません (それが最小であることをどのように知ることができるかを意味します)。