1

我有一个桌子女巫，看起来像这样：

--------------------------------------
| 索引 | 球员 | 日期 | 分数 |
--------------------------------------
| 1 | 一月 | 2013-01-13 | 5 |
--------------------------------------
| 2 | 彼得| 2013-01-13 | 6 |
--------------------------------------
| 3 | 克拉斯 | 2013-01-13 | 5 |
--------------------------------------
| 4 | 基斯 | 2013-01-13 | 7 |
--------------------------------------
| 5 | 威廉| 2013-01-13 | 8 |
--------------------------------------
| 6 | 约翰 | 2013-01-13 | 4 |
--------------------------------------

现在我想做一些棘手的事情，为了像 2013-01-14 的比赛那样打下一场比赛，我们想让 2 支球队得分相等。

每个日期期间有 12 名球员，因此 2013 年 1 月 13 日是 12 名球员，而 2013 年 1 月 14 日仍然有相同的球员。

他们必须分成 2 支球队，所以 12 / 2 = 6。每支球队有 6 人。现在这不是问题，问题在于两支球队的总分必须相等或接近。

如果 12 名球员的所有分数都是 77，那么 2 支球队的总分数必须几乎相等，这样 77 / 2 = 38,5

球队 1 - 球员 6 - 总分 37

队 2 - 球员 6 - 总分 40

最后查询输出必须是这样的：

-----------------------------------------------------------
| 索引 | 球员 | 日期 | 分数 | 团队 |
-----------------------------------------------------------
| 1 | 一月 | 2013-01-13 | 5 | 1 |
-----------------------------------------------------------
| 2 | 彼得| 2013-01-13 | 6 | 1 |
-----------------------------------------------------------
| 3 | 克拉斯 | 2013-01-13 | 8 | 1 |
-----------------------------------------------------------
| 4 | 基斯 | 2013-01-13 | 7 | 1 |
-----------------------------------------------------------
| 5 | 威廉| 2013-01-13 | 5 | 1 |
-----------------------------------------------------------
| 6 | 约翰 | 2013-01-13 | 6 | 1 |
-----------------------------------------------------------
| 7 | 格瑞特 | 2013-01-13 | 6 | 2 |
-----------------------------------------------------------
| 8 | 马杰| 2013-01-13 | 6 | 2 |
-----------------------------------------------------------
| 9 | 莎拉 | 2013-01-13 | 8 | 2 |
-----------------------------------------------------------
| 10 | 埃尔斯 | 2013-01-13 | 7 | 2 |
-----------------------------------------------------------
| 11 | 艾伦 | 2013-01-13 | 5 | 2 |
-----------------------------------------------------------
| 12 | 史蒂文 | 2013-01-13 | 8 | 2 |
-----------------------------------------------------------

和

-----------------------------------------------------------
| 团队 | 分数 | 日期 | 球员 |
-----------------------------------------------------------
| 团队 1 | 37 | 2013-01-13 | 6 |
-----------------------------------------------------------
| 团队 2 | 40 | 2013-01-13 | 6 |
-----------------------------------------------------------

在#Danack 的一些启发下，我做了这个：

$difference = 10;
$team_smnstlln = array();
for($q=0; $q<1000; $q++){
    
    $players = array();
    
    $team_smnstlln[$q] = array(
                                'team1' => array(),
                                'team2' => array(),
                                'total' => 0
                              );
    
    $count1 = 0;
    for($w=0; $w<6; $w++){
        $player = pick_random(true);
        $score1 = $team_smnstlln[$q]['team1'][$player] = $data[$player]['score'];
        $count1 = $count1 + $score1;
    }
    
    $count2 = 0;
    for($w=6; $w<12; $w++){
        $player = pick_random(true);
        $score2 = $team_smnstlln[$q]['team2'][$player] = $data[$player]['score'];
        $count2 = $count2 + $score2;
    }
    
    if($count1 > $count2){
        $total = $count1 - $count2;
    }
    elseif($count2 > $count1){
        $total = $count2 - $count1;
    }
    else{
        $total = 0;
    }
    
    $team_smnstlln[$q]['total'] = $total;
    
    if($team_smnstlln[$q]['total'] == 0){
        $difference = 0;
        $winner = $q;
        break;
    }
    elseif($team_smnstlln[$q]['total'] < $difference){
        $difference = $team_smnstlln[$q]['total'];
        $winner = $q;
    }
    
}

echo "Kleinst gekozen set met score verschil van $difference punten. array $winner is gekozen<br>";

$team1 = $team_smnstlln[$winner]['team1'];
$team2 = $team_smnstlln[$winner]['team2'];

print_r($team1);
print_r($team2);

// random player picker

function pick_random($gonogo){
    
    global $players;
    
    $go = true;
    $total_players = 11;
    
    while($go){
        
        $player = rand(0, $total_players);
        
        if(!in_array($player, $players)){
            $players[] = $player;
            $go = false;
        }
        
    }
    
    return $player;
    
}

此代码运行 1000 个不同的团队设置。当得分差达到 0 时，它将停止并与最好的平等球队比赛相呼应。否则，当没有 0 差异时，它将返回最低结果

4

3 回答 3

4

正如moonwave99 所说，在PHP 中执行此操作比在SQL 中执行此操作要好得多。

问题是这是一个很难解决的问题。您可以通过重新提出您的问题来看到这一点：

“一个队的6名球员和另一队的6名球员的什么组合，得分差异最小？”

从 12 名球员中挑选 6 名球员的组合数为 (12! / 6!) 或 665,280 种组合，每种组合都需要计算得分差异。

您需要检查所有可能的组合，并计算每个组合的分数以找到“最佳”组合。

//An array to record whether each player has already been selected for a combination
$playersChosen = array();

//Initialise the array
for($x=0 ; $x<12 ; $x++){
    $playersChosen[$x] = FALSE;
}

//Need to store lowest score somewhere - and have a flag for the first calculation
$lowestScore = FALSE;


chooseAnotherPlayer(6, 0);

//$GLOBALS['bestCombination'] - will now contain the best combination of players.


//Recursive function that either:
//goes through each player in turn and then calls itself or 
//calculates the 'score' when all the players are chosen for one team
//$playersToChoose - how many players left to choose.
//$minimumPlayerNumber - index to start searching for players not yet chosen - as the choice,  3 + 5 is identical to 5 + 3
function chooseAnotherPlayer($playersToChoose, $minimumPlayerNumber){

    //We have 6 pl
    if($playersToChoose == 0){
        //Calculate Score from which players are selected in $GLOBALS['playersChosen']
        if($lowestScore === FALSE ||
            $score < $lowestScore){
            $GLOBALS['bestCombination'] = $GLOBALS['playersChosen'];  //Arrays are copied by value, not reference
//So this saves a snapshot of the best selection.
        }
        return;
    }

    //Go through each of the players
    for($x=$minimumPlayerNumber ; $x<12; $x++){
        //Select them if they're available
        $playerAvailable = selectPlayer($x);
        if($playerAvailable == TRUE){
                    //Pick another player
            chooseAnotherPlayer($playersToChose - 1, $x + 1);
                    //Release this player, so he's available for other combinations
            unselectPlayer($x);
        }
    }
}

function selectPlayer($x){
    if($GLOBALS['playersChosen'][$x] == TRUE){
        //Player has already been selected in this combination.
        return FALSE;
    }

    return TRUE;
}

如果您不介意花几秒钟来处理该代码将完全解决您的问题。但是，如果您需要快速，最好随机选择团队，评估“分数”并进行足够的迭代以获得合理的结果。

$playersChosen = array();

resetArray();

$playersToChose = 6;
$lowestScore = FALSE;

for($n=0 ; $n<10000 ; $n++){
    chooseAnotherPlayers(6);
    resetArray();
}

function chooseAnotherPlayer($playersToChoose){

    if($playersToChoose == 0){
        //Calculate Score from which players are selected in $GLOBALS['playersChosen']
        if($lowestScore === FALSE ||
            $score < $lowestScore){
            $GLOBALS['bestCombination'] = $GLOBALS['playersChosen'];
            return;
        }
    }

    selectPlayerAtRandom($x);
    chooseAnotherPlayer($playersToChose - 1);
}

function selectPlayer($x){

    $playerSelected = FALSE;

    while($playerSelected == FALSE){

        $x = rand(0, 12 - 1);

        if($GLOBALS['playersChosen'][$x] == FALSE){
            $GLOBALS['playersChosen'][$x] = TRUE;
            return $x;
        }    
    }

}

function resetArray(){
    for($x=0 ; $x<12 ; $x++){
        $GLOBALS['playersChosen'][$x] = FALSE;
    }
}

除非您需要让团队精确匹配，否则即使只涵盖了一小部分不同组合，由于标准差和分布背后的数学，这可能会给您非常接近的结果。

您可以通过“经验法则”确定可接受的总分差是多少，然后搜索直到找到满足该标准的玩家组合或运行最大搜索时间（可能生成一个提醒搜索超时，并且匹配不均匀）。

于 2013-01-14T11:06:26.567 回答
1

这在 SQL 中很容易做到，并且在数据库中做到这一点有一定的优势——特别是，数据库可以利用并行性。以下是其中一个团队的 6 名团队成员。其余的应该很容易弄清楚：

select t1.index, t2.index, t3.index, t4.index, t5.index, t6.index,
       (t1.score+t2.score+t3.score+t4.score+t5.score+t6.score) as TeamScore
from t t1 join
     t t2
     on t1.index < t2.index join
     t t3
     on t2.index < t3.index join
     t t4
     on t3.index < t4.index join
     t t5
     on t4.index < t5.index join
     t t6
     on t5.index < t6.index cross join
     (select cast(sum(score)/2 as integer) as score from t) as Half
where Half.Score - TeamScore in (0, 1)
order by (Half.score - TeamScore)
limit 1
于 2013-01-14T14:42:55.927 回答
0

触发以下查询，它将在团队 1 中放入 6 条记录

 update table1 t1 set t1.team="1" where id IN(
    SELECT y.id
      FROM (SELECT t.id,
                   t.scores,
                   (SELECT SUM(x.scores)
                      FROM table1 x
                     WHERE x.id <= t.id) AS running_total
             FROM table1 t
         ORDER BY t.id) y
     WHERE y.running_total > (select * from (SELECT SUM(scores)/2 FROM table1) as sum) 
    ORDER BY y.id);

现在下面的查询会将其他 6 条记录放入团队 2

update table1 t1 set t1.team="2" where id NOT IN(
    SELECT y.id
      FROM (SELECT t.id,
                   t.scores,
                   (SELECT SUM(x.scores)
                      FROM table1 x
                     WHERE x.id <= t.id) AS running_total
             FROM table1 t
         ORDER BY t.id) y
     WHERE y.running_total > (select * from (SELECT SUM(scores)/2 FROM table1) as sum) 
    ORDER BY y.id);
于 2013-01-14T12:53:20.127 回答