Apenas procurando um pouco de direção, percebo que o exemplo dado é possível de ser resolvido usando a iteração de força bruta, mas estou procurando uma solução mais elegante (ou seja, matemática?) Que poderia potencialmente resolver exemplos significativamente maiores (digamos, 20x20 ou 30x30). ). É inteiramente possível que isso não possa ser feito, e eu tive muito pouco sucesso em propor uma abordagem que não dependa da força bruta ...

Eu tenho uma matriz (chame de A) que é nxn. Desejo selecionar um subconjunto (chamá-lo de B) de pontos da matriz A. O subconjunto será composto por n elementos, onde um e apenas um elemento é obtido de cada linha e de cada coluna de A. A saída deve fornecer uma solução ( B) tal que a soma dos elementos que compõem B é o valor máximo possível, dadas essas restrições (por exemplo, 25 no exemplo abaixo). Se forem encontradas várias instâncias de B (isto é, soluções diferentes que fornecem a mesma soma máxima), a solução para B que possui o maior elemento mínimo deve ser selecionada.

B também poderia ser uma matriz de seleção que é nxn, mas onde apenas os n elementos desejados são diferentes de zero.

Por exemplo: se 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 seria

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

No entanto, se A =

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

B =

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

Como o elemento mínimo de B é 3, que é maior que para

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

ou

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

que também somam 9