Ich arbeite aktuell an einem kleinen Projekt und bräuchte Hilfe.
Stellt euch folgenden Datensatz vor
Die Zahlenwerte sind immer aufsteigend sortiert. Außerdem gibt es immer genau so viele Zahlenwerte wie Spalten.
Alle Spalten (A-E) müssen einem Wert zugeordnet werden. A kann also z.B. die Werte 20, 90, 100, 120 oder 130 haben. Allerdings ist nach einer Zuordnung diese Zeile gesperrt.
Beispiel: A bekommt den Wert 90
A kann nur einen Wert bekommen (hier im Beispiel die 90) und die Zeile wo die 90 steht ist für die anderen Spalten dann gesperrt (B dürfte also zB keine 22 mehr bekommen).
Jetzt soll das so optimiert werden, dass die zugeordneten Werte von A-E in ihrer Summe so gering wie möglich sind. In diesem Beispiel wäre die Lösung: A=20, B=22, C=40, D=80, E=78 (Summe=240).
Mein Problem: In diesem Beispiel gibt es 120 (Fakultät von 5) mögliche Kombinationen. Das ist mit einem Programm schnell berechnet und kein Problem. Hätten wir jetzt aber z.B. A-J mit jeweils 10 möglichen Werten gibt es schon ungefähr 3,6 Mio (Fakultät von 10) Möglichkeiten. Dann wirds also schwer das in akzeptabel Zeit zu berechnen.
Ich brüte jetzt schon einige Tage über dem Problem. Gibt es einen Algorithmus, um das effizient auszurechnen oder bleibt wirklich nur das „Durchprobieren“.
Vielleicht fällt hier ja jemandem was ein.