Алгоритм - Попытка сбалансировать уровни командного мастерства, имея равное количество игроков.

Question

У меня есть 3 команды, у них есть 2 игрока, 3 игрока и 7 игроков. На боковых линиях 18 игроков, ожидающих назначения.

Каждый игрок имеет свой собственный уровень квалификации, то есть уровень 1 не собирается побеждать уровень 10.

Я хочу сбалансировать команды по 10 игроков в каждой. И я хочу постараться, чтобы все 3 команды были одинаково умелыми. Но я не хочу удалять игроков уже в команде.

Но я не уверен, как бы это сделать. Я также не уверен, есть ли простой ответ, или это будет дорого вычислять.

Уровень квалификации - это число, которое у меня уже есть. Все команды имеют равное количество игроков. Это означает, что уровень навыка является единственным изменяющимся числом.

Пример есть. В команде 13 игрока и общий уровень мастерства 4. В команде 2 6 игроков и общий уровень мастерства 8. В команде 3 8 игроков и общий уровень мастерства 9.

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

Answer 1

Это выглядит для меня так, как будто вы пытаетесь разделить (несколько) набор чисел ("уровни умений") на блоки одинакового размера ("команды"), чтобы средние значения ("общий уровень умений") были близки к равным насколько это возможно.

Чтобы решить эту проблему, я бы начал с вычисления среднего уровня мастерства, который представляет собой сумму уровней мастерства, деленную на количество игроков, называющих это число. s, Если есть m Всего команд, каждая с k игроки, давая в общей сложности m*k игроков, то целевой уровень квалификации для каждой команды k*s,

Так как ваши команды уже частично заполнены, проблема, которую вы создали, основана на вашем примере.

У меня есть 3 команды, у них есть 2 игрока, 3 игрока и 7 игроков. На боковых линиях 18 игроков, ожидающих назначения.

является следующим:

• Команда А, с текущим уровнем квалификации a нужно 8 игроков, чтобы p1 + ... + p8 + a = 10*s
• Команда B, с текущим уровнем квалификации b нужно 7 игроков, чтобы q1 + ... + q7 + b = 10*s
• Команда C, с текущим уровнем квалификации c нужно 3 игрока, чтобы r1 + r2 + r3 + c = 10*s

Для решения проблемы грубой силы сначала найдите игроков для команды C, а затем используйте оставшихся игроков, чтобы решить для команд A и B.

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

Answer 2

Здесь невозможно дать четкий ответ, потому что действительно важно то, насколько точна схема ранжирования и удовлетворяет ли она некоторым логическим свойствам.

Аддитивность: если рейтинг является идеальным, то он, вероятно, будет в некотором смысле аддитивным. Мое мышление исходит из бриджа, но подойдет любая задача, где игроки могут быть ранжированы и могут формировать группы. Так что было бы неплохо, если бы игрок 10 и 1 ранга, когда он объединился, подойдет для пары, состоящей из игроков 5 и 6 ранга. (Ранжирование мостов может быть более точным в логическом смысле, чем я читал.)

Синергия: Работают ли некоторые вместе лучше, чем другие в группе? Опять же, это вопрос ранжирования, потому что ваш рейтинг с одним человеком может быть лучше, чем с другими. Здесь часто есть синергетический аспект. В качестве примера, избегая мостика, гольф приходит на ум. Поместите двух человек вместе на поле для гольфа, если один человек - это тот тип, который постоянно разговаривает, а другому нужно молчать, чтобы сконцентрироваться, тогда по логике они будут плохо играть вместе.

Answer 3

Прагматичный подход, который даст вам хороший ответ, состоит в том, чтобы назначить игрока с самым высоким рейтингом команде с самым низким рейтингом, пока не будут назначены все игроки, где вы вычисляете ранг команды путем суммирования рангов ее игроков.