我有下面的球员数组和他们的分数。我想把他们分成两个相等的小组，尽可能使总得分相等。
E。G输出应为:
team a =球员id的505,481,510，总分为6
team b =球员id的504,509,513，总分为6
你能帮我指出正确的方向如何实现这一点吗?
谢谢
Array
(
[0] => Array
(
[match_id] => 664
[0] => 664
[player_id] => 505
[1] => 505
[Points] => 4
[2] => 4
)
[1] => Array
(
[match_id] => 664
[0] => 664
[player_id] => 481
[1] => 481
[Points] => 1
[2] => 1
)
[2] => Array
(
[match_id] => 664
[0] => 664
[player_id] => 510
[1] => 510
[Points] => 1
[2] => 1
)
[3] => Array
(
[match_id] => 664
[0] => 664
[player_id] => 504
[1] => 504
[Points] => 1
[2] => 1
)
[4] => Array
(
[match_id] => 664
[0] => 664
[player_id] => 509
[1] => 509
[Points] => 4
[2] => 4
)
[5] => Array
(
[match_id] => 664
[0] => 664
[player_id] => 513
[1] => 513
[Points] => 1
[2] => 1
)
)
所以这个问题是一个分区优化问题，猜猜看，它是np完全的!因此，您应该真正指定是需要最佳结果还是可接受的结果，因为它在算法和计算时间方面有很大的不同。如果你有一个非常小的数据集，最好的结果可以很快计算出来，但如果你的团队很大，这可能是一个真正的痛苦。
今天我感觉很精确(加上我不喜欢模糊和启发式lol)，所以我给你一个算法来计算最佳分割。它遍历所有可能的团队组合，并为每个团队计算权重(点数)差异，返回可能差异最小的团队。
你可以改进这个算法，如果他找到一个零(最好的分裂)，或者只枚举组合而不是排列，但是渐近复杂性是一样的，所以我就不麻烦了。
享受class SplitTeams {
private $_split_weight;
private $_split_teams;
private $_players;
public function __construct($players) {
$this->_players = array();
foreach ($players as $p) {
$this->_players[$p['player_id']] = $p;
}
}
public function getTeams() {
$this->_list_permutations(array_keys($this->_players), array());
$half = (int) (count($this->_split_teams) / 2);
$team_a = array_slice($this->_split_teams, 0, $half);
$team_b = array_slice($this->_split_teams, $half);
return array($team_a, $team_b);
}
private function _calculate_diff($list) {
$sum_team_a = 0;
$sum_team_b = 0;
for ($i = 0; $i < count($list); $i++) {
if ($i < (count($list) / 2))
$sum_team_a += $this->_players[$list[$i]]['Points'];
else
$sum_team_b += $this->_players[$list[$i]]['Points'];
}
return abs($sum_team_a - $sum_team_b);
}
private function _list_permutations($list, $perm) {
if (count($list) == 0) {
/* calculate the weight for this split */
$w = $this->_calculate_diff($perm);
if (($this->_split_weight === null) ||
($this->_split_weight > $w)) {
/* this is a candidate solution */
$this->_split_weight = $w;
$this->_split_teams = $perm;
}
print "PERM: " . implode("; ", $perm) . " - weight $w'n";
return;
}
for ($i = 0; $i < count($list); $i++) {
// slice array
$sublist = $list;
$a = array_splice($sublist, $i, 1);
$this->_list_permutations($sublist, array_merge($perm, $a));
}
}
}
$Data = array(
array('player_id' => 505, 'Points' => 4),
array('player_id' => 481, 'Points' => 1),
array('player_id' => 509, 'Points' => 3),
array('player_id' => 510, 'Points' => 1),
array('player_id' => 504, 'Points' => 1),
array('player_id' => 513, 'Points' => 2));
$s = new SplitTeams($Data);
$teams = $s->getTeams();
print_r($teams);
Array
(
[0] => Array
(
[0] => 505
[1] => 481
[2] => 510
)
[1] => Array
(
[0] => 509
[1] => 504
[2] => 513
)
)
UPDATE实际上我是开玩笑的，这个算法需要11秒8个玩家，1分钟9个玩家，10分钟10个玩家:)