Como adicionar números em uma matriz para obter o resultado mínimo? - c ++, algoritmo, matriz

Isso é mais um problema algorítmico / matemático, mas espero implementar uma solução em C ++.

Suponha que eu tenha uma matriz assim, onde os pontos representam números inteiros:

   W  X  Y  Z
A  .  .  .  .
B  .  .  .  .
C  .  .  .  .
D  .  .  .  .

Como produziria o resultado mínimo se eu tivesse que escolher um número de cada coluna, de modo que haja no máximo um número de cada linha?

Por exemplo, eu poderia escolher AW BX CY DZ ou AZ BX CY DW mas não AW BW CZ DZ

A abordagem da força bruta parece levar n! cálculos. Existe uma maneira mais rápida? Eventualmente, eu gostaria de adicionar números em matrizes de tamanho ~ 60.

Além disso, todos os números variam de 0 a 256.

Respostas:

E se você preferir não codificá-lo, vocêsempre poderia usar outra publicação "trabalhosa e gentil. Esta em Haskell, resolve uma matriz aleatória de 60x60 em menos de dois décimos de segundo no meu laptop antigo. Que ótimo algoritmo!

import Data.Algorithm.Munkres
import Data.Array.Unboxed
import Data.List (transpose)

solve n matrix =
hungarianMethodInt (listArray ((1,1),(n,n)) $ concat $ transpose matrix)