[CamelCase]

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!

[ProgMaster]

Linke, rechte Seite???
Was hat das mit sem Rucksackproblem zu tun?
Wofür brauchst Du eine Treenode?

[CamelCase]

Also ich habe mir gedacht das Rucksackproblem mit einem binären Baum zu lösen. Linke und rechte Seite meine ich das linke und rechte Kind eines Knotens.

public class TreeNode{
private TreeNode rechts;
private TreeNode links;
private int _wert;
private int _gewicht
}

Das maximale Gewicht darf z.B. 10 kg betragen. Diesen Wert speichere ich in der rootNode(nach dem ich eine erstellt habe) danach vergleiche ich das Gewicht in der root mit dem gewicht des ersten Items in meiner ArrayListe[]. Ist das Gewicht(Item) kleiner als das Gewicht der root, erstelle ich einen neuen Knoten bei root.rechtesKind und speichere das neue Gewicht(rootGewicht- ItemGewicht) im neuen Knoten ab, darüber hinaus ein neues linkes Kind in dem das rootgewicht gespeichert wird. Also soll heißen, die rechte Seite beinhaltet den bepackten rucksack, so würde ich gerne mit Rekursion den alle möglichen Kombinationen, wie ich den Rucksack befüllen könnte durchlaufen. Beim Rückschritt in einer static variable den maximalen wert speichern und somit herausfinden, wie der maximale Wert möglich ist.

[CamelCase]

Vielleicht noch eine Information, irgenwie muss ich dann noch das Item das im Baum(rucksack) quasi abglegt wurde aus der List löschen um die Gegenstände nicht doppelt zu verwenden. Wie gesagt dies ist momentan meine Lösungsidee und benötigt noch den ein oder anderen feinschliff....

[ProgMaster]

Ich sehe den Sinn nicht. Was soll Dir die TreeNode bringen?
Denke Du bist total auf dem Holzweg.

Schau Dir doch die Lösungen für das Rucksackproblem an und versuche diese zu implementieren.

[CamelCase]

Okay denke ich probiers dann mal mit greedy.
Aber trotzdem denke ich, dass es mit einem binären Baum lösbar wäre, vl etwas schwierig diese Lösung bei einem kurzen Überflug der Fragestellung fest zu halten.

Nur so zur Begründung meiner These.

ArrayList[] myItems;
Item a = new Item(String name,int wert, int gewicht) // Laptop, 200,3
Item b = new Item(String name,int wert, int gewicht) // Teschenr., 50,1

10kg // rootNode mit maximalem Gewicht
/ \ //rechtes und linkes Kind
/*links unverändert*/ 10 7 //rechts 10kg - eingepacktem laptop(3kg)
/ \ /\
10 7 6 //minus eingepackte, taschenr.

hoffe, dass du meinen Ansatz jetzt besser verstehen kannst. Also das linke Kind bleibt immer unverändert, das rechte Kind ist das Gewicht welches eingepackt werden darf minus dem gewicht des gegenstandes. Wurde etwas eingepackt, wird das nächste gewicht von dem aktuellen noch erlaubtem einzupackendem gewicht abgezogen. So könnte man mit Hilfe der Rekursion alle möglichen Bepackungsmöglichkeiten durchlaufen und der Rückschritt in der Rekursion wäre dann das Backtracking. Aber wie gesagt ich probier einfach weiter, falls ich meine Überlegung ausprogrammiert habe, stelle ich sie drauf.

mfg

[Pain12345]

Du behandelst das bekannte Problem P = NP.
Du musst alle Items mit allen kombinieren um das beste Ergebnis zu bekommen

[ProgMaster]

Um alle Permutationen zu durchlaufen brauchst Du keine TreeNode.
Je nachdem wieviele Elemente Du hast, kann das eine endlose Rechnerrei werden.
Das ist Overhead.

Um NP-harte Probleme effizient zu lösen, gibt es Approximationsalgorithmen, die Dir ein nahezu perfektes Ergebnis in Polynomialzeit liefern. IT-Neulingen muss man schon früh beibringen, dass es kontraproduktiv ist das "viereckige Rad neu zu erfinden".

[CamelCase]

ok danke erstmal für eure antworten! werde mich demnach mal nach deinen empfehlungen umschauen, um eine lösung zu finden!