Hallo Leute!
Kann mir vl jemand auf die sprünge Helfen, ich möchte kein Quellcode oder so, eher einen Aha-effekt
!
Ich befasse mich derzeit mit dem Rucksackproblem. Ich möchte also einen Rucksack mit verschiedenen Objekten bepacken. Diese Objekte haben einen Wert und ein Gewicht als Attribut(z.B Item(Taschenrechner- Wert 10Euro, Gewicht 0,5 kg) und mein Rucksack hat ein maximales Gewicht mit welches ich ihn bepacken darf. Die Fragestellung nun, wie ich den Rucksack bestmöglichst bepacke um ein maximalen Wert zu beinhalten.
Ich bin mir nun nicht ganz sicher ob ich das richtig verstanden habe, aber meines Wissens, könnte ich das Problem(Rucksackproblem, Backtracking-rekursiv) lösen in dem ich mir folgendes überlegt habe:
1. Meine Klassen sind: Item(Wert,Gewicht,Name), Rucksack(max-Gewicht),
TreeNode(links, rechts, gewicht, wert)
2. Die erstellten Items speichere ich in der Klasse Rucksack in einer ArrayList[].
3. Dann gehe ich die Liste durch und vergleiche das gewicht des items ArrayList[i] im ersten Schritt mit der root-node in dem ich das max-gewicht gespeichert habe.
4. Einpacken in die rechte Seite(root gewicht minus item gewicht ist dann im rechten kindknoten als gewicht gespeichert), nicht einpacken auf der linken Seite usw.
Nun habe ich totale Schwierigkeiten bei der Implementierung, also könnte mir vl jemand auf die Sprünge helfen, oder mich Informieren, ob ich auf dem Holzweg bin??
Vielen Dank schon mal für die Zeit zum durchlesen!