Ich versuche, einen sehr einfachen gierigen Algorithmus für das Rucksackproblem zu schreiben. Meine Eingaben sind zwei parallele Arrays. Ein Array enthält den Wert des Elements und das andere Array enthält die Gewichtungen.Gieriger Algorithmus für Rucksack in Java
Der Greedy-Algorithmus, den ich versuche zu schreiben, würde folgendermaßen aussehen: Überprüfen Sie, welches Element den höchsten Wert hat, und legen Sie dieses in den Rucksack. Setzen Sie dann den Wert dieses Elements auf Null. Überprüfen Sie erneut, welcher Artikel den höchsten Wert hat und legen Sie ihn in den Rucksack, wenn der Rucksack ihn noch halten kann. Wenn es es halten kann, setze den Wert wieder auf Null (nachdem du es eingefügt hast) und suche wieder nach dem höchsten Wert. Wenn dieser Rucksack es nicht mehr halten kann, dann beende einfach das Programm.
Ich weiß, dass es viele bessere gierige Algorithmen gibt, aber das scheint mir ziemlich einfach zu sein und ich denke, ich könnte das schaffen. Mein Problem ist, dass ich das gesamte Werte-Array durchlaufen muss, um den maximalen Wert zu finden. Dann, wenn ich es gefunden habe, lege ich es in den Rucksack und setze den Wert auf Null. Aber das Problem ist dann, dass ich zurück in die for-Schleife gehen muss, um das neue höchstwertige Element zu finden und dieses in den Rucksack zu legen. Aber ich weiß nicht, wie ich das machen würde.
Ich schreibe dies in Java.
Vielen Dank für die Antwort. Ich weiß, dass es eine Reihe von Möglichkeiten gibt, den Knapsack mit einem gierigen Algorithmus zu lösen, und ich habe bereits einen mit dem höchsten Verhältnis von Wert/Gewicht gesehen und benutzt. Ich wollte nur versuchen, alle Arten zu programmieren, da ich ein absoluter Anfänger bin. Das Problem mit der Sortierung zuerst und dann nur durch sie durchlaufen ist, dass mein Gewicht Index dann nicht mehr entspricht meinem Wert Index, so dass ich nicht mehr überprüfen kann, ob es immer noch in den Rucksack passt. Ich dachte, dass die Art, wie ich es tun würde, ein Workaround für dieses Problem sein könnte. – Tezen
Es gibt eine Entsprechung zwischen den Gewichten und Werten (d. H. Sie können nicht beliebig neu angeordnet werden). Im Moment klingt es so, als würden Sie die Gewichte und Werte in separaten Arrays speichern und versuchen, diese Korrespondenz nur in der Reihenfolge der Arrays zu erzwingen. Sie könnten diese Informationen kapseln, indem Sie eine einfache Klasse erstellen, die Wert/Gewicht eines Elements enthält. Sie können dann ein Array dieser Objekte erstellen und sortieren, ohne manuell verfolgen zu müssen, welches Gewicht und welcher Wert zusammengehören. –