trovare la somma minima di matrice (n x n) che seleziona solo uno in ogni riga e colonna

Question

questo è un altro problema algoritmi relative alla programmazione dinamica

Qui è il problema:

trovare la somma minima della matrice in modo tale che seleziona uno in ogni riga e colonna

Ad esempio:

3 4 2

8 9 1

7 9 5

quello minimo: 4 + 1 + 7

Credo che la soluzione è flusso di rete (max flusso / min cut), ma penso che non dovrebbe essere così difficile come è

La mia soluzione: separata alla lista n [colonna], column1, column2 ... colonna n

poi punto (S) start -> column1 -> column2 -> ... -> Colonna n -> (E) punto finale e implementare max flusso / min cut

Answer 1

Questo è il Assegnazione problema che può essere considerato un caso speciale di peso minimo in perfetta corrispondenza grafici. Il modo classico per risolvere il problema di assegnazione è quello di utilizzare la ungherese Algoritmo .