Ich versuche gerade, Problem 18 des Projekts Euler zu lösen. Das Ziel ist:
Wenn Sie oben im unteren Dreieck beginnen und zu den benachbarten Zahlen in der darunter liegenden Reihe gehen, ist die maximale Summe von oben nach unten 23.
%Vor%Das heißt, 3 + 7 + 4 + 9 = 23.
Finden Sie die maximale Summe von oben nach unten im folgenden Dreieck:
%Vor%
Ich habe versucht, es mit dem folgenden Algorithmus zu lösen:
%Vor% Die Array-Werte enthalten alle Zahlen aus dem Dreieck, wobei values[0][0] das Element in der obersten Zeile und values[n][n] das letzte Element in der letzten Zeile ist.
Der Algorithmus verwendet den Ansatz, dass, wenn ich zum Beispiel in der letzten Zeile anfange und die Wahl zwischen 04 + 63 und 62 + 63 habe, die Summe des Feldes, in dem 63 war, auf 125 gesetzt wird, weil dies die höchste ist Menge. Dieser Algorithmus funktioniert für das kleine Dreieck, aber für das große Dreieck scheint es zu versagen. Ich bin mir nicht sicher warum und würde mich über jeden Hinweis freuen.
Ich glaube, dass die Linie:
%Vor%sollte
sein %Vor%weil Sie gerade nicht das letzte Element in jeder Reihe besuchen. Natürlich brauchst du dann nicht die Zeile
%Vor%weil es bereits in der Schleife gemacht wurde.
Ich kenne den richtigen Algorithmus nicht, aber es gibt einen einfachen Beweis von @Johns Kommentar zu der Frage, dass die beste lokale Wahl nicht unbedingt zur besten globalen Lösung führt.
Betrachten Sie dieses (extreme) Beispiel:
%Vor% Wenn Sie Ihren Algorithmus verwenden, würden Sie ganz links vom Pfad gehen und niemals die 1000 lesen, die müssen auf dem besten Pfad sein müssen.
Tags und Links java