Team balance

[inphaser]

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

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

Заранее очень благодарен.

[Akina]

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

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