Формализация задачи на оптимизацию.

[alpha]

Формализация задачи на оптимизацию.

Есть футбольная комманда, в которой есть игроки. у каждого игрока есть несколько позиций. На каждой позиции у игрока очки. Надо построить состав команды с максимальным количеством очков.
Упрощений пример. Комманда с 3мя позициями из 4х человек.
1.Нападающий – 5000 очков
2.Нападающий – полузащитник – 6000 - 6000
3.Полузащитник – защитник -7000 - 7000
4.Защитник – 2000
Надо построить схему команды из 3х человек: защитник, полузащитник, нападающий
Правильная схема: 1(5000)-2(6000)-3(7000). Но как ее получить алгоритмически?
Не могу придумать функцию, которую на пустить к максимуму. У меня получается куча человек, которые играют на куче мест, и которые не должны повторятся(т.е. если мы выбрали уже человека на позицию, то в других позициях он не участвует).

Если кто помнит университетский курс, помогите формализовать задачу.

-~{}~ 22.10.07 18:20:

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

 

[StUV]

когда у одного человека совпадает количество голосов на разных позициях

полагая такие позиции для одного игрока взаимоисключающими - получишь тем же алгоритмом набор вариантов с одинаковым максимумом

 

[alpha]

Так если у одного человека совпадают количество очков на разных позициях, непонятно в какую его тулить. Тогда, наверное и будет задача оптимизации.
А если у игрока на разных позициях разное количество очков, то мы вибираем позицию где у него больше всего очков. И задача решается одним проходом по списку игроков(у игрока теперь одна позиция с максимальным количеством очков), упорядоченных по убыванию очков и расстановке игроков по позициям.
Этот вариант конечно неправильный, но зато простой. Проект бесплатный, скучный, шеф разницы в математических построених не улавливает, поэтому сойдет

 

[StUV]

alpha
можно тупым вложенным циклом пройтись по всем перестановкам и выбрать максимум
(число вложений - количество игроков, итерации каждого цикла - по позициям игрока)

-~{}~ 23.10.07 15:49:

зы: ессно, пропуская итерации с взаимоисключающими позициями разных игроков