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.
|