![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
109вот, кстати, задачка, с которой я в своё время столкнулся по поводу игрушки vga planets.
итак, имеем 11 разных рас и 11 игроков, желающих играть той или иной расой в той или иной степени (выраженной, скажем, в процентах). задача - найти такое распределение игроков по расам, чтобы суммарное "щастье" было максимально. точнее говоря, найти алгоритм, который будет это делать быстрее, чем простым перебором.
иными словами, имеется квадратная матрица NxN, удовлетворяющая условиям:
- все элементы матрицы принадлежат отрезку [0,1]
- сумма элементов каждой строки равна 1
- строки можно переставлять местами
требуется: найти алгоритм, вычисляющий максимальное значение суммы элементов главной диагонали и порядка строк, соответствующего этой сумме, имеющий наименьший порядок зависимости от N. N2 вполне пойдёт.
итак, имеем 11 разных рас и 11 игроков, желающих играть той или иной расой в той или иной степени (выраженной, скажем, в процентах). задача - найти такое распределение игроков по расам, чтобы суммарное "щастье" было максимально. точнее говоря, найти алгоритм, который будет это делать быстрее, чем простым перебором.
иными словами, имеется квадратная матрица NxN, удовлетворяющая условиям:
- все элементы матрицы принадлежат отрезку [0,1]
- сумма элементов каждой строки равна 1
- строки можно переставлять местами
требуется: найти алгоритм, вычисляющий максимальное значение суммы элементов главной диагонали и порядка строк, соответствующего этой сумме, имеющий наименьший порядок зависимости от N. N2 вполне пойдёт.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Ркак наÑÑÐµÑ ÑÑÐ¼Ð¼Ñ ÑлеменÑов
Date: 2002-11-29 07:08 pm (UTC)Re: Ркак наÑÑÐµÑ ÑÑÐ¼Ð¼Ñ ÑлеменÑо
Date: 2002-11-30 07:20 am (UTC)ÐÐ.
Date: 2002-11-30 08:13 am (UTC)ÐодÑÑиÑÑваеÑÑÑ ÑÑмма каждого ÑÑолбÑа.
ÐаÑÐ¸Ð½Ð°Ñ Ñо ÑÑолбÑа Ñ Ð¼Ð°ÐºÑималÑной ÑÑммой - ÑÑавниваем вÑе ÑлеменÑÑ ÑÑого ÑÑолбÑа Ñ ÑлеменÑом на главное диагонали - еÑли болÑÑе, менÑем ÑÑÑоки меÑÑами. ÐÑи ÑÑолбÑÐ°Ñ Ñ ÑавнÑми ÑÑммами пÑидеÑживаемÑÑ ÐºÐ°ÐºÐ¾Ð³Ð¾-либо поÑÑдка - Ñлева напÑаво или наобоÑоÑ.
Re: ÐÐ.
Date: 2002-12-01 10:11 pm (UTC)РдалÑÑе
Date: 2002-12-02 06:52 am (UTC)Re: РдалÑÑе
Date: 2002-12-02 06:58 am (UTC)Ð¥ÑаниÑÑ Ð½Ðµ ÑолÑко макÑималÑ
Date: 2002-12-02 02:10 pm (UTC)Re: Ð¥ÑаниÑÑ Ð½Ðµ ÑолÑко макÑимал
Date: 2002-12-03 06:00 am (UTC)