Мне нужно разделить группу игроков на команды и сделать их как можно более "честными"

Question

У меня есть группа из 9 игроков со значениями (уровнями квалификации), которые я хочу разделить на 3 команды по 3, чтобы общий уровень квалификации каждой команды был как можно ближе к одинаковому.

Для группа, (1, 1, 3, 4, 4, 4, 4, 5, 10), лучшее расположение будет (10, 1, 1), (5, 4, 3), (4, 4, 4 ), где все 3 команды имеют общую стоимость 12.

Я взял колоду карт и вытащил 9 карт с этими значениями, отсортировал их по 10-1 и начал раздавать их. Если я просто чередую порядок каждого раунда раздачи, то есть первый раунд слева направо, следующий справа налево и т. Д. c .. Я получаю (10, 4, 3), (5, 4, 1), ( 4, 4, 1) для итогов 17, 10, 9. Итак, я подумал, что если я отсортирую команды после каждого раунда? Итак, я раздаю первый раунд, по-прежнему распределяя игроков по возрастанию, затем сортирую по возрастанию, а затем раздаю следующий раунд, пока все карты не сойдут. Это приводит к (10, 4, 1), (5, 4, 1), (4, 4, 3) для итогов 15, 10, 11. Немного лучше, но не лучшее расположение.

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

Вот мой код в php

<code>## Get the registered players

  $players = array(1, 1, 3, 4, 4, 4, 4, 5, 10);
  $total_players = count($players);


## Sort the array by skill level

rsort($players);

## Determine number of teams

$num_teams = ceil($total_players / 3);

## Distribute players on teams

$teams = array();
$team_num = 0;

foreach ($players as $player)
{
  $teams[$team_num]["players"][] = $player;
  $team_num++;

  if ($team_num == $num_teams)
  {
    # reset counter to 0
    $team_num = 0;

    # Sort the teams on total score
    foreach ($teams as $key => $team)
    {
      $total_skill = 0;
      foreach ($team["players"] as $player)
      {
        $total_skill += $player;
      }
      $teams[$key]["total_skill"] = $total_skill;
    }

    aasort_asc($teams, "total_skill");
    $teams = array_values($teams);
  }
}
## Display teams with total scores

echo "<pre>"; print_r($teams); echo "

";

Возможно, уже опубликовано решение, но мне не удалось найти правильные условия поиска. Я полагаю, что может быть решение, которое не имеет ничего общего с игроками и командами. Любая помощь или руководство будет наиболее ценно. Будьте здоровы

Я пробовал несколько алгоритмов перестановки. Они оба уничтожают память после примерно 10 элементов массива.

Answer 1

Вот алгоритм c ответа.

Допущения: 1. Максимальный размер команды варьируется от мин до мин + 1 (равно или только еще один) 2. Уровень мастерства всегда положительный, произвольно большой

Алгоритм - начальный / подготовительный:

1. Определение минимального и максимального размера команды
2. Определение количества команд на основе минимального и максимального размера команды
3. Итого все навыки в одну сумму.
4. Разделите общее количество навыков по количеству команд, чтобы получить средний навык для каждой команды.
5. Разделите общее количество навыков на # участников = средний навык для каждого.
6. Сортировка участников по уровню квалификации.

Алгоритм - сбор команд:

1. Определите размер этой команды (мин или макс), как вам нравится.
2. Взять ток Общее умение команды (сначала пусто = 0).
3. Добавление участника команды с самым высоким навыком.
4. Сравните сумму навыков в команде со средним для такого количества участников.
5. Если это выше среднего, добавьте следующего участника с низким уровнем навыка.
6. If th ниже среднего, добавьте следующий с конца высокого навыка.
7. Продолжайте 4-6, пока команда не заполнится.
8. Продолжайте с другими командами (1-7) до завершения.