|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Dan Raskovalov 2:5080/151.100 15 Jul 2001 23:36:44 To : Kluchnikov Eugene Subject : Matrix --------------------------------------------------------------------------------
KE> Имеется матрица n*n, все числа - байты, 15<n<150.
KE> Hеобходимо найти максимальную сумму по перестановке ( т.е. в каждой
KE> строке и в каждом столбце надо чтобы выбран был ровно один элемент). Саму
KE> перестановку искать необязательно - может быть это делает
KE> задачу NP-неполной? А то 150! перебрать за приемлемое время (5 сек) не
KE> кажется реальным.
Ключевое слово: паросочетание. Еще конкретней: венгерский алгоритм.
Bye, Kluchnikov.
--- FRACtal Station
* Origin: Все равно MustDie не брошу, потому что он хороший.. (2:5080/151.100)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/44613b52293d.html, оценка из 5, голосов 10
|