задачка

[109]

вот, кстати, задачка, с которой я в своё время столкнулся по поводу игрушки vga planets.

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

иными словами, имеется квадратная матрица NxN, удовлетворяющая условиям:
- все элементы матрицы принадлежат отрезку [0,1]
- сумма элементов каждой строки равна 1
- строки можно переставлять местами

требуется: найти алгоритм, вычисляющий максимальное значение суммы элементов главной диагонали и порядка строк, соответствующего этой сумме, имеющий наименьший порядок зависимости от N. N² вполне пойдёт.

Comments

Re: ОК.

[109.livejournal.com]

ну так, поставим мы максимальный элемент одного столбцп на диагональ. а дальше?

А дальше

[network-angel.livejournal.com]

делаем то же самое со следующим.

Re: А дальше

[109.livejournal.com]

что делать, если установка максимального элемента следующего столбца на диагональ требует свопа со строкой, чей диагональный элемент уже установлен?

Хранить не только максималь�

[network-angel.livejournal.com]

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

Re: Хранить не только максимал�

[109.livejournal.com]

получаем бинарный алгоритм, описанный в самом первом моём комментарии. к сожалению, он не гарантирует нахождение абсолютного максимума.