在C#中，我正在尝试编写一个算法，根据每个玩家的整数评分来平衡两个团队。
数据集如下：
Player 1: 1330
Player 2: 1213
Player 3: 1391
Player 4: 1192
Player 5: 1261
Player 6: 1273
Player 7: 1178
Player 8: 1380
Player 8: 1200
Player 10: 1252
我希望建立两组五名球员的团队，使得两个团队的总评分差异尽可能小，以便进行公平比赛。
为此，我想生成所有团队排列组合（每个排列组合都是两个由 5 名球员组成的团队）。但所有的 C# 排列组合示例都是用于组合像幂集之类的东西，而不是团队。
最有效的方法是什么？
0101010101 是一个有效的团队，但 0011000100 不是一个有效的团队。0101010101 与团队 1010101010 配对。private readonly int[] _playerRatings = new[] {1330, 1213, 1391, 1192, 1261, 1273, 1178, 1380, 1200, 1252};
private int CalculateTeamScore(int team)
{
var score = 0;
for (var i = 0; i < 10; ++i)
{
if ((team & 1) == 1)
{
score += _playerRatings[i];
}
team >>= 1;
}
return score;
}
private bool IsValidTeam(int team)
{
// determine how many bits are set, and return true if the result is 5
// This is the slow way, but it works.
var count = 0;
for (var i = 0; i < 10; ++i)
{
if ((team & 1) == 1)
{
++count;
}
team >>= 1;
}
return (count == 5);
}
public void Test()
{
// There are 10 players. You want 5-player teams.
// Assign each player a bit position in a 10-bit number.
// 2^10 is 1024.
// Start counting at 0, and whenever you see a number that has 5 bits set,
// you have a valid 5-player team.
// If you invert the bits, you get the opposing team.
// You only have to count up to 511 (2^9 - 1), because any team after that
// will already have been found as the opposing team.
for (var team = 0; team < 512; ++team)
{
if (IsValidTeam(team))
{
var opposingTeam = ~team;
var teamScore = CalculateTeamScore(team);
var opposingTeamScore = CalculateTeamScore(opposingTeam);
var scoreDiff = Math.Abs(teamScore - opposingTeamScore);
Console.WriteLine("{0}:{1} - {2}:{3} - Diff = {4}.",
team, teamScore, opposingTeam, opposingTeamScore, scoreDiff);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication1
{
class Player
{
public int PlayerId { get; set; }
public int PlayerBit { get; set; }
public int PlayerScore { get; set; }
public override string ToString()
{
return string.Format("Player: {0} Score: {1}\n",PlayerId,PlayerScore);
}
}
public class Program
{
public static void Main(string[] args)
{
const int maxDiff = 15;
var players = new List<Player> { new Player() {PlayerId = 1, PlayerBit = 1<<0, PlayerScore = 1330},
new Player() {PlayerId = 2, PlayerBit = 1<<1, PlayerScore = 1213},
new Player() {PlayerId = 3, PlayerBit = 1<<2, PlayerScore = 1391},
new Player() {PlayerId = 4, PlayerBit = 1<<3, PlayerScore = 1192},
new Player() {PlayerId = 5, PlayerBit = 1<<4, PlayerScore = 1261},
new Player() {PlayerId = 6, PlayerBit = 1<<5, PlayerScore = 1273},
new Player() {PlayerId = 7, PlayerBit = 1<<6, PlayerScore = 1178},
new Player() {PlayerId = 8, PlayerBit = 1<<7, PlayerScore = 1380},
new Player() {PlayerId = 9, PlayerBit = 1<<8, PlayerScore = 1200},
new Player() {PlayerId = 10, PlayerBit = 1<<9, PlayerScore = 1252}};
var maxTeam = players.Max(x => x.PlayerBit);
var maxBit = maxTeam * 2 - 1;
var team = from t1 in Enumerable.Range(0, maxTeam) where getBitCount(t1) == 5 select t1;
var match = team.Select(x => new { t1 = x, t2 = maxBit - x });
foreach (var m in match)
{
var t1 = players.Where(x => (x.PlayerBit & m.t1) == x.PlayerBit);
var t2 = players.Where(x => (x.PlayerBit & m.t2) == x.PlayerBit);
var t1Score = t1.Sum(x => x.PlayerScore);
var t2Score = t2.Sum(x => x.PlayerScore);
if (Math.Abs(t1Score - t2Score) < maxDiff)
{
Console.WriteLine("Team 1 total score {0} Team 2 total score {1}", t1Score, t2Score);
Console.WriteLine("{0} versu \n{1}\n\n", string.Join("", t1.Select(x => x.ToString()).ToArray()), string.Join("", t2.Select(x => x.ToString()).ToArray()));
}
}
Console.Read();
}
private static int getBitCount(int bits)
{
bits = bits - ((bits >> 1) & 0x55555555);
bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
return ((bits + (bits >> 4) & 0xf0f0f0f) * 0x1010101) >> 24;
}
}
}
maxDiff == 1，那么 Math.Abs(t1.totalScore - t2.totalScore) <= maxDiff 怎么可能为真呢？71 显然不小于 1。你确定你发布的代码就是你正在运行的代码吗？ - Jim Mischel这基本上是分割问题的优化版本，该问题是NP难的。
然而，由于n = 10相当小，您仍然可以找到所有排列并找到答案，对于更大的n，您可以使用快速且易于实现的贪婪近似算法，该算法也显示在维基页面上。下面我只展示了一个用于暴力枚举n = 10情况以找到答案的样例代码。虽然它是用C++编写的，但里面没有什么特别的东西，所有操作符/数组在C#中都是相同的，您应该自己完成翻译工作，复杂度为O(2^10 * 10)。
#include<bits/stdc++.h>
using namespace std;
int a[10] = {1330,1213,1391,1192,1261,1273,1178,1380,1200,1252};
vector<int> team1, team2;
int ans = 1<<28, T1, T2;
int bits(int x){
int cnt = 0;
while(x){ cnt += x&1; x>>=1;}
return cnt;
}
int main(){
for(int i=0; i< 1<<10; i++){
if(bits(i) == 5){
int t1 = 0, t2 = 0;
for(int x = i,y=(1<<10)-1-i, j=0; x; x>>=1,y>>=1, j++) {
t1 += (x&1)*a[j];
t2 += (y&1)*a[j];
}
if(ans > abs(t1-t2)){ ans = abs(t1-t2); T1 = i; T2 = (1<<10)-1-i;}
}
}
for(int i=1; T1 || T2; T1>>=1, T2>>=1, i++) {
if(T1&1) team1.push_back(i);
if(T2&1) team2.push_back(i);
}
printf("Team 1: ");
for(int i=0; i<5;i++) printf("%d ", team1[i]);
puts("");
printf("Team 2: ");
for(int i=0; i<5;i++) printf("%d ", team2[i]);
puts("");
printf("Difference: %d\n", ans);
return 0;
}
~符号，它应该在那里。我明白你所说的有关有符号整数的问题，尽管算法仍然可以工作。对手队伍的编号将是负数，这有点奇怪。通过编写var opposingTeam = (~team) & 0x3FF;很容易解决这个问题。无论如何，我很高兴你已经解决了它。 - Jim Mischelteam < Math.Pow(2, PlayerPool.Length)-1)，因此它会检查0到1022个团队。也就是说，它比需要的比较更多，并且会错过最后一个。它会将第31个团队与其对手团队（在我的代码中为-32）进行比较，然后稍后会将团队-32与团队31进行比较。没有必要进行两次检查。如果您使用条件team < (1 << (PlayerPool.Length - 1))，它将检查0到511个团队，这就是我的代码所做的。这与Math.Pow(2, PlayerPool.Length-1)相同。 - Jim Mischel