Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Rucksack packen!
Guten Abend,
sitze gerade an der packRec.java und ärgere mich an den Testfällen. Mir zeigen Testfall 2, 4 und 5 kontinuierlich mein Versagen^^. Ich habe die Aufgabe nach Anleitung gelöst und für alle meine Tests funktioniert meine Rekursion. Meine Programm funktioniert also soweit, wenn ich packRec aufrufe, dass es immer die höchstwertige Kombination heraussucht. Mein Programm funktioniert jedoch NICHT, wie in den Testfällen, wenn mittendrinnen irgendwo eingestiegen wird und ich weiß einfach nicht, wie ich das ändern könnte.
Ich erläutere es mal am 2. Test:
"
public static void test2(int[] sizes, int[] values) {
if (packRecAux(sizes, values, 0, 2) > 0)
System.out.println(“(2) FAILURE!”);
}
"
sizes.length = 4;
values.length = 4;
übriger Platz im Rucksack = 0;
current Item = 2;
aufgerufen wird die packRecAux!
meine Überlegung: in packRecAux kommt man mit Rucksack = 0 nur rein, wenn:
a) der Rucksack von Anfang an leer ist. Dann ist aber CurrentItem (wie in backRec initialisiert) das letzte Item in den Arrays. Das triff im Testfall nicht zu! Es müsste sein: Current Item = 3, dann würde mein Basisfall auch gescheit greifen…
b) der Rucksack ist durch das letzte Item voll geworden. Das bedeutet aber, dass zuvor schon entschieden wurde was gepackt wurde und was nicht, denn mein value-array sollte in so einem Fall genau über diese Information verfügen und jetzt einfach die Werte zusammenzählen, die nicht 0 im Array sind und die größer als Index Current Item sind…
ABER im Testfall wird erwartet, dass als Ergebnis 0 rauskommt, was ja total sinnlos ist, weil der Rucksack ja erwartet, dass wir mit dem letzten Item und nicht mitten drin beginnen.
Wo ist mein Denkfehler? 
Was ist mit den Basisfällen c) und d)?
Dein Basisfall scheint mir falsch zu sein. Es ist durchaus valide, dass der Rucksack voll ist (kein Platz mehr verfügbar), aber noch Items zur Verfügung stehen. Stell dir vor, du packst deinen Koffer für den Urlaub hast alles, was mit soll um dich gelegt und räumst es in den Koffer ein und plötzlich ist der Koffer voll, aber nicht alles, was du mitnehmen willst, ist drin. Das kann durchaus passieren.
In deiner Beschreibung von Punkt (b) scheint mir auch, dass du einen Denkfehler beim Rucksackproblem hast. Dein value-Array enthält die Werte aller Objekte unabhängig davon, ob sie eingepackt oder nicht eingepackt wurden.
Wenn du ein Item in den Rucksack packst, betrachtest du den Restrucksack als völlig neues Teilproblem, das du lösen musst (rekursiver Aufruf). Deine Aufgabe ist jetzt eben einen kleineren Rucksack mit weniger Items zu packen. Wenn du wieder ein Item rein packst, verringert sich wieder die Rucksackgröße. Aber das Programm weiß in den einzelnen Teilproblemen nicht, was vorher eingepackt wurde. Das Programm läuft solange, bis ein Basisfall erreicht wurde (also zum Beispiel ein Rucksack ohne Platz gefüllt werden soll). Du musst dir überlegen, was die Lösung für diesen Basisrucksack ist. Dieser Basiswert wird jetzt an das größere Problem (Rucksack war etwas größer und bestimmtes Item wurde eingepackt) zurückgegeben (das Ergebnis steht jetzt an der Stelle des Rekursionsaufrufs). An dieser Stelle kennst du quasi den besten Wert des kleineren Rucksacks und du kennst den Wert des Objekts, was du gerade in den Rucksack einpacken möchtest. Diese Werte musst du kombinieren, um den Wert des aktuellen Rucksacks zu bekommen, der ggf. wieder nur ein Teilproblem eines größeren Rucksacks war, dessen Wert jetzt ermittelt werden soll.
Jaja, immer das gleiche Spiel.
Völlig andere Überlegung, irgendetwas passt nicht, dann Anpassung der eigenen Überlegung bis zum grünen Haken, dann anpassen, bis eigene Überlegung gleich dem eigentlichen Weg ist und dann Abgabe^^
Dankeschön für eure Hilfe, eure Kommentare haben mich in die richtige Richtung gelenkt 