Mal wieder eine Unzulänglichkeit im Testcase?
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.
Aufgabe 8.2 (Rucksackproblem): 65%-Hürde
Nach mindestens einstündiger Analyse (an dieser Stelle ein Danke an iceman!) habe ich herausgefunden, warum der Testcase bei fast allen Leuten nicht mehr als 65% gibt, obwohl im Prinzip alles richtig ist.
Das Problem ist die Rückgabe der Partition in der Funktion [m]getPartition()[/m]: Als vernünftiger Mensch denkt man sich ja, dass das zurückgegebene Feld nur so groß sein sollte, wie es tatsächlich auch Elemente der Lösung enthält. Anscheinend erwartet der Testcase aber, dass die Länge des Arrays so groß sein soll, dass theoretisch alle Elemente reinpassen, die vorher mit [m]setElements()[/m] reingefüttert wurden. Die Partition wird dann also automatisch mit Nullen ausgefüllt, wenn die Lösung weniger Elemente enthält als insgesamt Elemente vorhanden sind.
Ich glaube jetzt aber nicht, dass das wirklich im Sinne der Aufgabenstellung ist - das ist bestimmt mal wieder ein Fehler im Testcase. :vogel:
Ich werde mal wieder eine E-Mail rausschicken, um das zu klären.
soll das array bei getPartition() jetzt pro lösung eine zeile haben oder für jedes lösungelement?! denn beim beispiel 1 2 3 3 gibt es ja 2 lösungen.
sollte das array dann z.B.:
array[0]=“1:2”;
array[1]=“3”;
oder dann für jede einzele ein element der lösung, also:
array[0]=“1”;
array[1]=“2”;
array[1]=“3”;
was man dann in der main wieder richtig formatieren kann oO
Ein Beispiel:
[m]
Elemente: {2, 3, 5, 6}
Rucksackgröße: 8
Eigentliche Lösung: {3, 5}
Testcase will aber: {0, 0, 3, 5}
[/m]
Also wegen dem scheiss hab ich mir jetz nun den halben Sonntag um die ohren geschlagen :#:
Props an Airhardt du wahrst der Erste 
stimmt…wenn ich die nuller mit ausgebe passts…deshalb hat er mir auch nur bei der rückgabe von elements 90% gegeben…
zimlich unlogisch mal wieder :wand: :wand: :wand: :wand:
Oben zu sehen, ein Ausschnitt aus der Vorlesung vom Marc! Daraus schließe ich, dass das mit den Nullen falsch ist:
Und zwar Summiert man über Elemente der Menge T, die wiederum Teilmenge von S ist… S sind die Elemente, die übergeben werden! Und die sind aus N und da sind keine Nullen dabei!
Somit ist die Testcase zu 99,99999… Prozent in dem Bereich FALSCH g :motz:
Naja, wenn sie meinen… Will mich nicht zu weit aus dem Fenster lehnen!
@Airhardt und iceman: Vielen Dank!
Bis dann!
So hab das jetzt mal geändert, jetzt sind es bei mir schon 95%. Danke an Airhardt für den guten Tip.
Fehlen vielleicht jemand anderem auch diese letzten 5%? Bzw hat schon jemand diese Hürde bei sich gelöst?
Also IMHO ist das mit den Nullen auch falsch. Ist ja, wie “vielleicht” schon angemerkt hat, keine Teilmenge der Element-Menge mehr.
Bevor ich mein Programm so verunstalte, hab ich lieber nur 65% :motz:
Außerdem steht nirgends was über die Größe des Arrays, das getPartitions() zurückliefern soll, das können sie also schlecht als Fehler werten…
Aber trotzdem respekt an Airhardt für die Detektivarbeit!
Also ich hab das Prob grad mit meim Uebungsgruppenleiter besprochen und wir sind zu dem Schluss (ohne aber den Code des Testcase zu haben) gekommen, dass das Testcase ein Array der Form { 0, 1, 1, 1} erwartet, wobei 0 wohl bedeutet, dass das Element nicht dabei ist und 1 bedeutet dass das Element dabei ist. Die Aufgabenstellung ist aber so, dass die Loesung, die Werte der benoetigten Elemente zurueckzugeben durchaus richtig ist. Mein Uebungsleiter hat bereits eine Mail an seine Kollegen geschickt dass die Testcases entsprechend angepasst werden.
Thanks an Tobias!!!
Ach ja, einfach noch Nullen anzuhaengen duerfte zwar die ArrayOutOfBoundsException im Testcase umgehen, aber richtig duerfte das nicht sein…
@liwo: ah! Ja, so macht das sogar wieder Sinn. Das ist typisches Informatiker Denken eigenltich 
Macht das aufstellen des Ergebnisarrays deutlich einfacher.
Wenn meine Werte {2,3,5,10} sind, dass ich z.B. für “5” als Ergebnis {1,1,0,0} zurückgebe.
Wie dem auch sei, was bleibt ist:
Warum zum Henker kann man Aufgaben nicht eindeutig spezifizieren? Was ist daran bitte so schwer?
OK, das wäre natürlich auch eine Möglichkeit. Allerdings hätte man da das Problem, dass diese Maske auf das sortierte Feld angewandt wird. Da das Sortieren der Elemente aber möglicherweise erst innerhalb von [m]setElements()[/m] stattfindet, könnte das zu Irritationen führen, wenn man von außerhalb ein unsortiertes Feld von Elementen eingibt!
Denn wenn man in [m]setElements()[/m] nicht die Referenz übernimmt, sondern die Daten kopiert, hat man innen ein anderes Array als außen - und wenn man dann das innere Array sortiert, bleibt das äußere unverändert.
Außerdem wäre dann die Anweisung „Return the elements that contribute to a successful rucksack solution in sorted order (ascending)“ schlicht falsch.
Und noch was: Wenn sie wirklich eine Maske aus Nullern und Einsern erwarten, warum hat iceman dann trotzdem 100% gekriegt, obwohl er ein mit Nullern „gepolstertes“ Array von Elementen zurückgeliefert hat und keine Maske?
Auch wahr…
Womit wir jetzt bei dem aller letzten und einzigen Schluss bleiben:
Einfach schlechte, weil zu ungenaue Aufgabenstellungen 
Das ist uns auch aufgefallen. Trotzdem ist die Ausgabe des Testcase (ich hab sie gesehen) eindeutig so zu interpretieren und die Aufgabenstellung ist anders zu interpretieren…
Weil das Testcase hier sagt: „Moeglicher Fehler, erwartet wird 0 oder 1“ oder so was in der Art, es wohl aber nicht als Fehler wertet…
So, geben jetzt auch einfach {0,0,0,…,1,2,3} zurück statt {1,2,3} und jetzt 100%.
Schade um die viele Zeit gestern. Denke ab nächster Woche fang ich immer freitag an, aber mit den aufgaben, die ich am selben abend abgeben muss
Also vielen dank nochmal für die fleisige Fehleranalyse.
Gruß und einen schönen abend.
Thomas
Das würde ich dir nicht raten… Wenn dann mal wieder der Server down ist… uiuiui
zur not mail an algo9@…
Mal ein subjektiver Kommentar: ich finde den Algorithmus mit der Matrix sowieso lame. So toll war die rekursive Definition zwar auch nicht, aber immerhin kein lästiges Indextralala. :>
Java: >50 Zeilen
Scheme: 9 Zeilen
Haskell: 5 Zeilen?
Ich kann noch eine Verbesserung drauflegen:
garnicht: 0 Zeilen
Hoho, dieses garnicht wurde wohl extra fürs Rucksackproblem designed. 