Solo buscando un poco de dirección, me doy cuenta de que el ejemplo dado es posible resolverlo mediante la iteración de fuerza bruta, pero estoy buscando una solución más elegante (¿es decir, matemática?) Que podría potencialmente resolver ejemplos significativamente más grandes (por ejemplo, 20x20 o 30x30). ). Es totalmente posible que esto no se pueda hacer, y he tenido muy poco éxito en encontrar un enfoque que no se base en la fuerza bruta ...

Tengo una matriz (llámala A) que es nxn. Deseo seleccionar un subconjunto (llámelo B) de puntos de la matriz A. El subconjunto constará de n elementos, donde se toma uno y solo un elemento de cada fila y de cada columna de A. La salida debe proporcionar una solución ( B) de tal manera que la suma de los elementos que componen B es el valor máximo posible, dadas estas restricciones (por ejemplo, 25 en el siguiente ejemplo). Si se encuentran múltiples instancias de B (es decir, diferentes soluciones que dan la misma suma máxima), se debería seleccionar la solución para B que tiene el elemento mínimo más grande.

B también podría ser una matriz de selección que es nxn, pero donde solo los n elementos deseados no son cero.

Por ejemplo: si A =

<code>|5 4 3 2 1|
|4 3 2 1 5|
|3 2 1 5 4|
|2 1 5 4 3|
|1 5 4 3 2|
</code>

=> B sería

<code>|5 5 5 5 5|
</code>

Sin embargo, si A =

<code>|5 4 3|
|4 3 2|
|3 2 1|
</code>

B =

<code>|3 3 3|
</code>

Como el elemento mínimo de B es 3, que es más grande que para

<code>|5 3 1|
</code>

o

<code>|4 4 1|
</code>

que también suman ambos a 9