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
|