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.
5.5 BackpackRec
Hey,
Ich bekomme momentan bei meiner Abgabe ein gelbes Aufrufezeichen, bei der Abgabe fuer BackpackDp hab ich hingegen nen schoenen Haken. Nun ist meine Frage die folgende: Da ja bei beiden Algorithmen dieselben Ergebnisse erwartet werden, werden diese auch mit denselben Parametern getestet, oder? Ich selbst konnte bisher noch keine Faelle finden, bei denen zum einen unterschiedliche Ergebnisse rauskommen und zum anderen die Ergebnisse von meinen haendisch ausgerechnetet Ergebnissens abweichen.
Moeglicherweise liegt, mein Fehler in den Hilfmethoden, was ich aber nicht vermute, da ich die Methoden der rekursiven Variante einfach nur kopiert habe.
Hat jemand eine Idee, wo das Problem liegen koennte?
public class BackpackTest
{
public static void main(String[] args)
{
int[] sizes0 = {};
int[] values0 = {};
checkPack(sizes0, values0,0,0);
checkPack(sizes0, values0,4,0);
int[] sizes1 = {4};
int[] values1 = {3};
checkPack(sizes1, values1, 2, 0);
checkPack(sizes1, values1, 4, 3);
checkPack(sizes1, values1, 6, 3);
int[] sizes2 = {4,4,3,2,1};
int[] values2 = {2,3,2,1,1};
checkPack(sizes2, values2, 2, 1);
checkPack(sizes2, values2, 3, 2);
checkPack(sizes2, values2, 4, 3);
checkPack(sizes2, values2, 5, 4);
checkPack(sizes2, values2, 6, 4);
checkPack(sizes2, values2, 7, 5);
checkPack(sizes2, values2, 8, 6);
/**
* Reversed order of 2nd test
*/
int[] sizes3 = {1,2,3,4,4};
int[] values3 = {1,1,2,3,2};
checkPack(sizes3, values3, 2, 1);
checkPack(sizes3, values3, 3, 2);
checkPack(sizes3, values3, 4, 3);
checkPack(sizes3, values3, 5, 4);
checkPack(sizes3, values3, 6, 4);
checkPack(sizes3, values3, 7, 5);
checkPack(sizes3, values3, 8, 6);
int[] sizes4 = {3,5,3,4,4};
int[] values4 = {2,2,2,3,2};
checkPack(sizes4, values4, 2, 0);
checkPack(sizes4, values4, 3, 2);
checkPack(sizes4, values4, 4, 3);
checkPack(sizes4, values4, 5, 3);
checkPack(sizes4, values4, 6, 4);
checkPack(sizes4, values4, 7, 5);
checkPack(sizes4, values4, 8, 5);
checkPack(sizes4, values4, 9, 5);
checkPack(sizes4, values4, 10, 7);
checkBaseCase(4,1,false); // no base Case
checkBaseCase(5,0,false); // no base case
checkBaseCase(5,-1,true); // base case
checkBaseCase(0,-1,true); // base case
checkBaseCase(0,1,true); // fully packed
checkBaseCase(-1,1,true); // for negative backpack values on packRec/packDp
/**
* You can handle the last item in the base case so that there will be no
* unnecessary recursive call, but it is indeed specified otherwise.
*/
/*
checkBaseCase(4,0,false); // last item
checkBaseCase(5,-1,true); // should never happen
checkBaseCase(0,-1,true); // but end recursion
*/
checkSelectBetterResult(1,2,2);
checkSelectBetterResult(2,1,2);
checkSelectBetterResult(2,2,2);
checkSelectBetterResult(0,2,2);
checkSelectBetterResult(2,0,2);
checkSelectBetterResult(-1,0,0);
}
public static void checkSelectBetterResult(int a, int b, int exp)
{
int rec = BackpackRec.selectBetterResult(a,b);
int dp = BackpackDp.selectBetterResult(a,b);
System.out.println( ((rec == dp && dp == exp) ? "pass" :(
"\tfail\trec: " + rec + " dp: " + dp + " exp: " + exp)));
}
public static void checkPack(int[] sizes, int[] values, int backpackSize, int exp)
{
int rec = BackpackRec.packRec(sizes,values,backpackSize);
int dp = BackpackDp.packDp(sizes,values,backpackSize);
System.out.println( ((rec == dp && dp == exp) ? "pass" :(
"\tfail\trec: " + rec + " dp: " + dp + " exp: " + exp)));
}
public static void checkBaseCase(int spaceLeft, int currentItem, boolean exp)
{
boolean rec = BackpackRec.isBaseCase(spaceLeft, currentItem);
boolean dp = BackpackDp.isBaseCase(spaceLeft, currentItem);
System.out.println( ((rec == dp && dp == exp) ? "pass" :(
"\tfail\trec: " + rec + " dp: " + dp + " exp: " + exp)));
}
}
1 Like
Ich bin mir ziemlich sicher, dass du hier keinen Hausaufgaben-Code posten solltest…
Edit: gelöscht von Chayyam, hier stand Mist.
Hab ich nicht gemacht ;-). ist alleine eine Testklasse und in keinster Weise fuer die Hausaufgabe, bis auf die Verifikation von Ergebnissen fuer bestimmte Testfaelle, von Relevanz.
OK 
Nein, ich hab (leider) immer noch einen Ausrufezeichen.
Noch eine andere Frage: Soll der Algorithmus fuer Itemgroessen kleiner 1 (also 0 oder sogar negativ) funktionieren?
hab dasselbe problem, die values werden richtig ausgerechnet, haba uch diverse Testfälle ausprobiert, trotzdem gelber haken 
@ AuD-Dozenten und Forenadmins:
Ich bitte um Entschuldigung wegen meines vorigen Posts im Thread. Es sieht so aus, als wäre mein Account gehackt worden, um mich bei meiner Arbeit zu stören, indem man in meinem Namen geheime Testfälle verrät oder aufdringliche PNs an andere User (besonders Nyx) schreibt. Eigentlich wollte ich als Tutor in AuD etwas länger als ein Semester arbeiten, aber solche Dinge will ich echt nie wieder erleben. Deswegen bitte ich die Admins, meinen Account nach Möglichkeit zu löschen. Ich hoffe trotzdem, mit euch allen weiterhin vertrauensvoll arbeiten zu können.
@ vaiquero: Geh am besten in die Rechnerübung, dort hilft man dir gerne weiter.
hat einer idee
@xenexi hast du das problem lösen können oder immer noch gelb?
Ne noch nicht, ich hab noch ein bisschen herumprobiert, aber nichts gefunden.
hmm bei mir dasselbe, hab schon in alle richtungen porbiert den Code anzupassen. Tutor hatte auch keine IDee dazu 
Server Probleme Est???
also nachdem jetzt die Server wieder online sind und ich die datei nochmal hochgeladen hab war es ein grüner Haken… also scheint wohl nen EST fehler gewesen zu sein?!? Super wenn es tatsächlich so ist, hab nämlich schon an meinem Verstand gezweifelt, schade um die bestimmt 8 - 10 stunden die am Wocheneinde reingeflossen sind um den Fehler zu finden… 
Joa bei mir leider auch aber immerhin gehts jetzt. 
Fertig mit AuD fuer diese Woche
checkBaseCase(4,0,true); // last item spuckt bei mir fail aus.
→ fail rec: false dp: false exp: true
Diese Zeile ueberprueft ja die Methode isBaseCase, sobald ich hier versuche etwas zu veraendern, kommen aber mehr Fehlermeldungen und die main-Testfaelle funktionieren auch nicht mehr.
Ist hier der Testfall falsch oder hab ich irgendwas uebersehen?
Genau sollte die Methode ja ueberpruefen, ob der Code fuer currentitem == 0 das richtige macht.
Aber gibt es nicht ein Item mit dem Index 0?
Verbessert mich, wenn ich hier Mist von mir gebe
Ich selbst habe das letzte Item im Basisfall selbst behandelt, weil ich damit 2 rekursive Aufrufe weniger habe, da im letzten Aufruf mit nur einem Item sowohl packCurrentItem(…) und tryOtherItem( …) aufgerufen wird, welche jeweils packRecAux(…) wiederaufrufen und dann erst abbrechen. Ist daher eine kleine Optimierung, aber jetzt,wo du’s sagst, bin ich mir nicht ganz sicher, ob das erwuenscht ist. Ich denke du hast aber recht, wenn du die Anweisungen ganz genau befolgst und der Basisfall fuer currentItem=0 false zurueckgibt.
PS: falls jemand noch was dazu sagen koennte, waere ich dankbar.
Theoretisch ist es egal, wie der Basisfall implementiert wurde, solange sich die Methode “packRec(int sizes[], int values[], int size)” korrekt verhält. Praktisch würde ich den Basisfall so implementieren, wie er in dem Code beschrieben wurde, da das EST die Methode “isBaseCase(int spaceLeft, int currentItem)” eventuell separat testet:
/* Handle the base cases:
* a) We tested all items
* b) There are no items to begin with
* c) The backpack is full
* d) The backpack didn't have any space to begin with
*/Joa, das hab ich mir auch gedacht, nachdem kristin gefragt hat. Ich hab den Test dementsprechend geaendert.^^
Hi,
ich wollte mal fragen, ob sich in sizes und values die Werte bzw. die Größe des Gegenstandes an der Stelle item befindet?
Ja. (bzw. genau anders rum, in sizes die Groesse und in values die Werte - aber ich vermute, du hast dich da nur verschrieben)