ähm ... whatisthematrix.com ... klingt eher als seist du auf der Suche nach einem Algorithmus.
ein Wert aus jeder der m Zeilen - max. k Werte aus einer Spalte
PHP-Code:
m=8; n=20; k=5;
matrix = new Array(
1, 2, 3, 4, 5, 6, 7, 8,
11, 12, 13, 14, 15, 16, 17, 18,
...
191,192,193,194,195,196,197,198,
201,202,203,204,205,206,207,208
);
das einfachste wär natürlich brute force (brutale Gewalt) = für alle Kombinationen mit n Werten aus verschiedenen Zeilen - erst Vailiditäts-Check (max. k Werte je Spalte?), dann Summe berechnen:
PHP-Code:
ergebnisse = new Array();
zaehler = new Array();
zaehler.length = m;
// kombi mit der ersten passenden Kombination initialisieren
// Ergebnis: kombi = (0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3)
kombi = new Array();
kombi.length = n;
for(zeile=0,wert=-1; zeile<n; zeile++)
{
if (!(zeile % k)) wert++; // alle k Zeilen wert erhöhen
kombi[zeile] = wert;
}
maxkombi = '-'; maxsumme=0;
do
{
// maximal 5 Werte aus einer Spalte?
// (= max. 5x den gleichen Buchstaben)
// dabei gleich die Summe bilden
summe = 0;
for(spalte=0; spalte<m; spalte++)
zaehler[spalte] = 0;
for(ok = true, zeile=0; ok && zeile<n; zeile++)
{
spalte = kombi[zeile];
if (++zaehler[spalte] > k)
ok = false;
else
summe += matrix[zeile*m + spalte];
}
// ja: Summe mit bisherigem Maximum vergleichen
if (ok && summe>maxsumme)
{
maxsumme = summe;
maxkombi = kombi.join(',');
}
// Hochzählen
for(zeile=n-1; zeile>=0; zeile--)
{
wert = kombi[zeile]+1;
if (m==wert) wert = 0; // Überlauf bei m
kombi[zeile] = wert;
if (wert) break; // kein Überlauf: Abbruch
}
} while(zeile>=0) // Abbruch bei Überlauf an erster Stelle
alert ('Kombination mit der höchsten Summe: '
+ maxkombi + '; Summe=' + maxsumme);
Bei den Dimensionen deiner Matrix wären das etwa 20^8 = 25,6 Milliarden Durchläufe; und das ist wohl weniger akzeptabel. Selbst wenn dein Rechner zehn Millionen Durchläufe pro Sekunde schaffen sollte, braucht das Skript über 40 Minuten, um ein Ergebnis auszuspucken - und bis dahin hat dein Browser das Skript schon x-mal unterbrochen, um dich zu fragen ob es weiter ausgeführt werden soll.
Aber es gibt ein paar einfache Methoden, das etwas zu beschleunigen, und ein paar kompliziertere. Der flotteste Algorithmus, der mir auf die Schnelle einfällt ist dieser hier; eine Art quadriertes Backtracking:
Der erste Schritt für alle Beschleunigungsmaßnahmen bei diesem Problem: Man erstelle eine Index-Matrix, in der für jede Zeile die Indizes der Werte in absteigender Reihenfolge gespeichert werden.
ein Beispiel - 3x3-Matrix; es darf maximal ein Wert aus jeder Spalte kommen:
m=n=3; k=1;
matrix = new Array(
8, 15, 22,
3, 17, 9,
12, 3, 21
);
die Index-Matrix sieht so aus: (
2, 1, 0,
1, 2, 0,
2, 0, 1
);
Höchster Wert in der ersten Zeile ist die 22 an dritter Stelle = Position 2,
danach kommen 15 an Position 1 und die 8 ganz vorne (Position 0).
Die anderen Zeilen werden analog erstellt.
Dann fängt die Iteration an ... es werden jeweils für die ersten n Zeilen der Matrix die erste gefundene zulässige Index-Kombination samt der dazugehörigen Teilsumme gespeichert. Dadurch dass wir die Werte über die Index-Matrix absteigend sortiert haben, bekommen wir automatisch die beste.
bei obigem Beispiel ohne Vailidierung:
Zeile 0:
2 (22); weitere Kombinationen: 1 (15) - 0 (8)
Zeilen 0-1:
2, 1 (39);
weitere gültige Kombis:
2, 0 (22+3=25)
0, 1 (8+17=25)
1, 2 (15+9=24)
1, 0 (15+3=18)
0, 2 (8+9=17)
8, 15, 22,
3, 17, 9,
12, 3, 21
Nu kommt die Validierung dazu:[list=1][*]Die Kombination 2,1,2 (22+17+21 = 60) ist ungültig.[*]Also gehen wir zu vorigen Zeile zurück und suchen uns die nächst niedrigere gültige Kombination bis zu der Zeile: 2,0 (22+3=25)
Die Differenz zur höchsten Kombination 2,1(39) ist 14.[*]Bevor die jetzt verwurstet wird, schauen wir erst einmal nach, ob wir nicht einen Wert in der dritten Zeile finden, bei dem die Differenz geringer (oder gleich) ist; alles was >=21-14 ist passt also.
Die nächst niedrigere Zahl in der Zeile steht (wie uns die Index-Matrix sagt) an Position 0, es ist die 12. Das ist >=7[*]also schauen wir mal ob (2,1,1) gültig ist ... zwei Werte aus einer Spalte, also nicht.[*]nächste gültige zweizeilige Kombi + höchste aus Zeile 2: 2,0,2 (22+3+21 = 46) - passt aber auch nicht[*]nächste gültige zweizeilige Kombi ist die 0,1(8+17=25);
die Differenz zur vorigen Kombi ist 0. Also passt uns entweder die höchste aus der dritten Zeile oder alle gleichwerigen (die es nicht gibt)
0,1,2 passt aber schon; Wert: 8+17+21 = 46.[*]Wir haben eine Zahl aus der letzten Zeile hinzugefügt, damit ist die gültige Kombination mit der höchsten Summe gefunden.[/list=1]
Übrigens findet der brute-force-Algorithmus bei diesem Beispiel die gleiche Kombination, was aber nicht unbedingt sein muss.
Hier ist das etwa nicht der Fall:
matrix = new Array(
1,2,3,
1,2,3,
1,2,3
);
m=n=3; k=1;
brute force findet 0,1,2 mit Summe 6;
der andere Algorithmus wirft 2,1,0 mit der gleichen Summe aus.
---------------------------------------------------------------------------------
Zugegeben, der Algorithmus ist nicht ganz einfach zu implementieren; aber wenn du erst ein paar Monate JavaScript geübt hast und dann ein paar Tage Gehirnschmalz reinsteckst, kannst du hier ja mal das Ergebnis
präsentieren.
Für den Anfang bau dir erstmal ein Skript, das die Index-Matrix erstellt.
Im bruteforce-Skript habe ich auch noch ein paar Möglichkeiten zur Beschleunigung gelassen; die wirst du allerdings erst mit viel Übung oder durch ausgiebiges Nachdenken über die Möglichkeiten der Sprache entdecken. (Die gleichen Möglichkeiten bieten sich aufgrund der Ähnlichkeit der Sprachen auch in C und Konsorten sowie PHP und natürlich Java.)
Auf jeden Fall empfehle ich Dir die ausgiebige Lektüre des JavaScript-Bereiches im
selfHTML; da steht so ziemlich alles, was man über JavaScript wissen muss.
Ist auch prima als Nachschlagewerk geeignet; aber ich würd´s mir
runterladen, die neue Werbeschaltung ist ein wenig lästig.