Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 17.02.2011, 09:10
Новичок

Отправить личное сообщение для inphaser Посмотреть профиль Найти все сообщения от inphaser
 
Регистрация: 17.02.2011
Сообщений: 1

Team balance
Извиняюсь за неолимпиадность этой задачи, но, может быть, кто-то может подсказать направление, куда надо копать для решения задачи баланса команд.

Итак, дано n игроков (n кратно k), для каждого существует рейтинг ni, необходимо поделить игроков на m=n/k команд с равным количеством игроков таким образом, чтобы E(|mi - Eni/m|) была минимальной. Где mi - суммарный рейтинг i-той команды, Eni - сумма рейтингов всех игроков.

Заранее очень благодарен.
  #2  
Старый 17.02.2011, 15:02
Новичок

Отправить личное сообщение для Akina Посмотреть профиль Найти все сообщения от Akina
 
Регистрация: 26.11.2010
Сообщений: 5

Есть способ быстрого поиска решения, близкого к оптимальному.

Решается стандартная задача наполнения одного контейнера, допускающая переполнение. Из всех возможных решений с одинаковым отклонением выбирается то, в котором минимальное значение использованного элемента максимально.
После чего повторяется поиск решения для k-1 команд.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра