Hallo zusammen,
ich hab mir sogar ein Buch gekauft, welches mir aber bei diesem Problem leider nicht weiter helfen konnte.
Die Aufgabe lautet, man solle eine Matrix erstellen by radom und dann soll Zeile jeweils die höchste Zahl mit der möglichst höchsten Zahl vom nächsten Ergebnis addiert werden.
Aber jetzt kommt der haken:
Ein Punkt (i, j ) hat nur drei mögliche Nachfolger (i + 1, j − 1), (i + 1, j ), (i + 1, j + 1).
Beispiel: Für die Matrix:
7 2 2
2 5 6
4 1 0
1 5 0
lautet der optimale Weg (1,1), (2,2), (3,1), (4,2) mit der maximalen Summe 7 + 5 + 4 + 5 = 21.
Grad kommt mir dann eine kleine Idee:
Ich nehme von der ersten Matrix das höchste Element und dann versuche ich in seinen drei Möglichkeiten das nächst höchste davon zu nehmen.
Jetzt schau ich aber in der 2. Zeile, was dort das höchste wäre und was davon der vorherigste höchste vorgänger und je nachdem welcher es ist, entscheide ich mich dann dafür.
Wäre schonmal ein Anfang.
Für alle Fälle schon mal mein jetziger Code:
Besten Dank schonmal
NACHTRAG: Ein Fehler von mir, man soll nicht Backtraking sondern Dynamische Programmierung verwenden.
Zitat vom Tutor:"...berechnet erst eine Teillösungen,
und baut diese dann Stück für Stück zu einer Gesamtlösung zusammen,
quasi "bottom-up"."
ich hab mir sogar ein Buch gekauft, welches mir aber bei diesem Problem leider nicht weiter helfen konnte.
Die Aufgabe lautet, man solle eine Matrix erstellen by radom und dann soll Zeile jeweils die höchste Zahl mit der möglichst höchsten Zahl vom nächsten Ergebnis addiert werden.
Aber jetzt kommt der haken:
Ein Punkt (i, j ) hat nur drei mögliche Nachfolger (i + 1, j − 1), (i + 1, j ), (i + 1, j + 1).
Beispiel: Für die Matrix:
7 2 2
2 5 6
4 1 0
1 5 0
lautet der optimale Weg (1,1), (2,2), (3,1), (4,2) mit der maximalen Summe 7 + 5 + 4 + 5 = 21.
Grad kommt mir dann eine kleine Idee:
Ich nehme von der ersten Matrix das höchste Element und dann versuche ich in seinen drei Möglichkeiten das nächst höchste davon zu nehmen.
Jetzt schau ich aber in der 2. Zeile, was dort das höchste wäre und was davon der vorherigste höchste vorgänger und je nachdem welcher es ist, entscheide ich mich dann dafür.
Wäre schonmal ein Anfang.
Für alle Fälle schon mal mein jetziger Code:
Code:
class Matrix{
int n;
int m;
void eingabe (int n, int m) {
this.n=n;
this.m=m;
int array[][] = new int [n][m];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
array[i][j]=(int)(50*Math.random());
}
}
System.out.println("Matrix erstellt:");
System.out.println("Zeilen (m)= " + array.length);
System.out.println("Spalten (n) = " + array[1].length);
ausgabe(array);
}
void ausgabe(int[][] array) {
int rowSize = array.length;
int columnSize = array[0].length;
for(int i = 0; i <= n-1; i++) {
System.out.print("[");
for(int j = 0; j <= m-1; j++) {
System.out.print(" " + array[i][j]);
}
System.out.println(" ]");
}
System.out.println();
}
}
Besten Dank schonmal
NACHTRAG: Ein Fehler von mir, man soll nicht Backtraking sondern Dynamische Programmierung verwenden.
Zitat vom Tutor:"...berechnet erst eine Teillösungen,
und baut diese dann Stück für Stück zu einer Gesamtlösung zusammen,
quasi "bottom-up"."
Zuletzt bearbeitet: