Trouver le maximum de la somme des éléments de la matrice dans des lignes et des colonnes distinctes

Question

J'ai une matrice nxm et j'ai besoin de trouver le maximum de la somme de ses valeurs dans des lignes et des colonnes distinctes.

Par exemple compte tenu de la matrice suivante:

 m1 m2 m3 
n1 1 2 3 
n2 4 5 6 
n3 7 8 9 
n4 10 11 12 

Le maximum sera de 12 + 8 + 4 = 24

Notez que de trouver le maximum et en éliminant toutes les valeurs appartenant à cette colonne ou d'une rangée est pas une bonne solution car elle ne fonctionne pas dans tous les cas.

L'exception pour ci-dessus sera le suivant:

 m1 m2 
n1 17 1 
n2 18 15 

Si vous trouvez 18 et enlever 17 et 15, la somme sera de 18 + 1 = 19. tandis que 17 + 15 = 32 a une valeur plus élevée .

Une idée de l'algorithme pour cette question?

Answer 1

La solution consiste à utiliser l'algorithme hongrois. C'est un algorithme compliqué. Il y a une très bonne lecture sur ce sur youtube:

http://www.youtube.com/watch?v=BUGIhEecipE