Сплит PHP-массив на два равных набора, где сумма значений равна

Question

У меня есть следующий массив игроков и их очки. Я хочу разбить их на две равные команды, где сумма баллов должна быть равна, где это возможно.

Например, вывод должен быть:

команды а = игрок идентификаторы 505, 481, 510, общее количество очков составляет 6

команды б = игрок идентификаторы 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 
     ) 

) 

Answer 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 игроков :)