Ich versuche nach einem Algorithmus zu suchen, der mir hilft, die maximale Summe nicht benachbarter Elemente in einem 2D-Array zu finden. 1) http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/ 2) https://www.youtube.com/watch?v=UtGtF6nc35gMaximale Summe von nicht benachbarten Elementen in einem 2D-Array
Zum Beispiel in einem 1D-Array:
Für 1D-Arrays, ich hilfreiche Lösungen aus gefunden habe {3, 2, 6, 2, 10} Ich werde erhalten eine maximale Summe von 19, weil 3, 6 und 10 nicht benachbart sind.
Allerdings kann ich keine finden, die mir mit einem 2D-Array helfen kann. Wie kann ich die maximale Summe von Ganzzahlen in diesem Array ohne horizontale oder vertikale benachbarte Elemente finden? Diagonal benachbarte Elemente sind erlaubt.
Zum Beispiel:
[3, 2, 6, 2, 10]
[1, 5, 2, 5, 1]
[5, 1, 7, 2, 9]
[3, 9, 1, 8, 2]
Gibt es einen bestehenden Algorithmus dieses Problem zu lösen? Oder wäre es eine andere Methode, um dieses Problem zu lösen, wenn ich eine andere Datenstruktur anstelle eines 2D-Arrays verwende?
Haben Sie Vier-Wege-Nachbarschaft oder Acht-Wege? –
Entschuldigung für die Nichtangabe, horizontal und vertikal ist nicht erlaubt, aber diagonale Adjazenz ist erlaubt. –
Geht es um "wie" oder "wie mit bestmöglicher zeitlicher Komplexität"? Brauchen Sie das Maximum oder ist eine Näherung ausreichend? Über welche Größe von 2D-Arrays reden wir? –