PHPの配列を2つの等価集合に分割し、値の和が等しい場合

Question

以下のプレイヤーとそのポイントの配列があります。私は2つの同等のチームに分けたがって、ポイントの合計は可能な限り均等にする必要があります。

例えば、出力は次のようになります

チームA =プレイヤーIDの505、481、510、合計6

チーム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 
     ) 

) 

Answer 1

ありがとう、NP完全です！したがって、が最高のの結果を必要とするか、が許容できるの結果を必要とするかを実際に指定する必要があります。アルゴリズムと計算時間の点で大きな違いがあるからです。データセットが非常に小さい場合は、最善の結果を素早く計算することができますが、チームが大規模であれば本当の苦労かもしれません。

今日私は正確な感じがしていました（そして、私は曖昧さと経験則を好きではありません）ので、私はあなたに最高の分割を計算するアルゴリズムを与えています。可能なすべてのチームの組み合わせを通過し、チームごとにウェイト（ポイント）の差を計算し、できるだけ少ない差でチームを返す。

このアルゴリズムを改善するには、ゼロ（可能な限り最良の分割）が見つかるか、置換の代わりに組み合わせのみを列挙しますが、漸近的な複雑さは同じですので、私は気にしません。

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); 

出力楽しみなさい：UPDATE

Array 
(
    [0] => Array 
     (
      [0] => 505 
      [1] => 481 
      [2] => 510 
     ) 

    [1] => Array 
     (
      [0] => 509 
      [1] => 504 
      [2] => 513 
     ) 

) 

を実際に私が冗談を言っていた、このアルゴリズムは8人の選手、9人のプレーヤーのための1分、および10人のプレーヤーのため10分間11秒かかります:)