Poszukując odrobiny kierunku, zdaję sobie sprawę, że podany przykład jest możliwy do rozwiązania przy użyciu iteracji siły brute, ale szukam bardziej eleganckiego (tj. Matematycznego?) Rozwiązania, które potencjalnie mogłoby rozwiązać znacznie większe przykłady (powiedzmy 20x20 lub 30x30 ). Jest całkiem możliwe, że nie da się tego zrobić, a ja miałem bardzo mały sukces w podejściu do podejścia, które nie opiera się na brutalnej sile ...

Mam macierz (nazwij ją A), która jest nxn. Chcę wybrać podzbiór (nazwijmy go B) punktów z macierzy A. Podzbiór będzie składał się z n elementów, z których jeden i tylko jeden element jest pobierany z każdego wiersza iz każdej kolumny A. Wynik powinien zapewniać rozwiązanie ( B) tak, że suma elementów składających się na B jest maksymalną możliwą wartością, biorąc pod uwagę te ograniczenia (np. 25 w poniższym przykładzie). Jeśli znaleziono wiele instancji B (tj. Różne rozwiązania, które dają taką samą maksymalną sumę), należy wybrać rozwiązanie dla B, które ma największy minimalny element.

B może być również macierzą wyboru, która jest nxn, ale gdzie tylko n pożądanych elementów jest niezerowych.

Na przykład: jeśli 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 byłoby

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

Jeśli jednak A =

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

B =

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

Ponieważ minimalnym elementem B jest 3, który jest większy niż dla

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

lub

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

które jednocześnie sumują się do 9