trouver la somme minimale de la matrice (n x n) qui sélectionnent un seul dans chaque rangée et colonne

Question

est un autre problème lié à des algorithmes de programmation dynamique

Voici le problème:

trouver la somme minimale de la matrice donnée de telle sorte que dans une sélection de chaque rangée et colonne

Par exemple:

3 4 2

8 9 1

7 9 5

l'une de minimum: 4 + 1 + 7

Je pense que la solution est de flux réseau (débit max / coupe min) mais je pense qu'il ne devrait pas être aussi difficile que cela est

Ma solution: séparée à la liste n [colonne], colonne1, colonne2 ... colonne n

alors le point de départ (S) -> column1 -> column2 -> ... -> la colonne n -> (E) le point d'extrémité et mettre en coupe débit max / min

Answer 1

Ceci est Affectation problème qui peut être considéré comme un cas particulier de poids minimum correspondant de parfait graphiques. La méthode classique pour résoudre le problème d'affectation est d'utiliser le hongrois algorithme .