Wenn ich nur nach einer Richtung suche, stelle ich fest, dass das angegebene Beispiel mithilfe von Brute-Force-Iteration gelöst werden kann, ich suche jedoch eine elegantere (dh mathematische?) Lösung, die möglicherweise wesentlich größere Beispiele (z. B. 20x20 oder 30x30) lösen kann ). Es ist durchaus möglich, dass dies nicht möglich ist, und es ist mir nur sehr wenig gelungen, einen Ansatz zu finden, der nicht auf roher Gewalt beruht ...

Ich habe eine Matrix (nenne sie A), die nxn ist. Ich möchte eine Teilmenge (nenne es B) von Punkten aus der Matrix A auswählen. Die Teilmenge besteht aus n Elementen, wobei aus jeder Zeile und jeder Spalte von A genau ein Element entnommen wird. Die Ausgabe sollte eine Lösung liefern ( B) so, dass die Summe der Elemente, aus denen B besteht, der maximal mögliche Wert ist, wenn diese Einschränkungen gegeben sind (z. B. 25 im folgenden Beispiel). Wenn mehrere Instanzen von B gefunden werden (dh verschiedene Lösungen, die die gleiche maximale Summe ergeben), sollte die Lösung für B ausgewählt werden, die das größte minimale Element aufweist.

B könnte auch eine Auswahlmatrix sein, die nxn ist, bei der jedoch nur die n gewünschten Elemente ungleich Null sind.

Zum Beispiel: wenn 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 wäre

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

Wenn jedoch A =

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

B =

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

Als Minimalelement von B gilt 3, was größer ist als für

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

oder

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

die auch beide zu 9 summieren