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.6. RücksackDPZeigeLösung
Hallo, ich habe eine Frage wegen der letzten Aufgabe, weil es irgendwie nicht richtig funktioniert .
Was ich mache ist eine Schleife, die durch die Reihen läuft und eine Variable die die aktuele Spalte zeigt. Also am Anfang zeigt die Variable die Letzte Spalte.
Dann in der Schleife prüfe ich ob die current Zelle!=Zelle von vorheirchen Reihe und wenn das wahr ist packe ich i und mache ich die currentSpalte mit der groesse von Gegenstand i kleiner , wenn nicht packe ich nicht.
Weisst jemand was das Problem ist?
Die Ausgabe sieht so aus:
Backpack sizes -> 0 1 2 3 4 5 6
Item # 0 (v = 1, s = 3): 0 ? 0 ? 1 ? 1
Item # 1 (v = 2, s = 2): ? ? 2 ? 2 ? 3
Item # 2 (v = 2, s = 2): ? ? ? ? 4 ? 4
Item # 3 (v = 1, s = 2): ? ? ? ? ? ? 5
Packing item # 3 (v = 1, s = 2)
Packing item # 2 (v = 2, s = 2)
Packing item # 1 (v = 2, s = 2)
Backpack sizes -> 0 1 2 3 4 5
Item # 0 (v = 1, s = 5): ? ? ? ? ? 1
Packing item # 0 (v = 0, s = 0)
Not packing item # 0 (v = 0, s = 0)
Ich habe es auch erst mit einer Schleife probiert. Habe es aber nicht hingekriegt und es dann mit Rekursion gemacht.
Da rufst du dann die methode “zeigeloesung” mit verschiedenen eingabeparametern auf je nachdem, ob du deinen aktuellen gegenstand in den rucksack gepackt hast, oder nicht.
Weiß nicht, ob das die ideale Lösung ist, aber bei mir haben jedenfalls die testcases funktioniert.
Hoffe das hilft und, dass es einigermaßen verständlich formuliert war
Danke, ich werde probieren, aber ich würde es gerne auch iterativ machen um zu verstehen wo mein Fehler liegt.
Hat es jemand mit einer Schleife gemacht?
Mach dir dein Leben bitte nicht so kompliziert. Manche Probleme kann man gar nicht iterativ lösen.
Edit: Ich sehe meinen Fehler ein, finde die rekursive Lösung aber auch nicht viel komplizierter.
Dieses Problem aber schon! Und es rekursiv zu machen ist in diesem Fall unnötig kompliziert!
@ioio23
Es sieht so aus als würdest du das Item in der ersten Zeile weder packen noch nicht packen. Evtl. ist das deines Rätsels Lösung ;). Bedenke aber, dass du da keine „vorherige“ Zeile mehr hast, in der du nachschauen musst. Du musst dir also eine andere Regel ausdenken, wann du ein einzelnen Item in der ersten Zeile einpackst oder nicht einpackst.
Vom Prinzip her klingt deine Beschreibung richtig, musst halt bei den “Basisfällen” aufpassen, dass nichts übersehen und keine Array-Grenzen überschritten werden. Beim Test wird bei dir jedenfalls im ersten Fall der letzte Gegenstand ignoriert, anstatt nicht gepackt zu werden, ebenso beim zweiten Test (obwohl das in dem Fall der einzige Gegenstand ist und er gepackt werden sollte), da stimmt also irgendwas nicht.
Die letzten beiden Ausgaben(“Packing item # 0 (v = 0, s = 0)” und “Not packing item # 0 (v = 0, s = 0)”) gehören lediglich zum Interface Test, davon nicht irritieren lassen.
Welche denn? Mal abgesehen von nicht berechenbaren?
Wie würdest du denn z. B. eine kaskadenartige Rekursion (mir fällt da leider kein einfaches Beispiel ein, ich denke da an W-Zyklen beim Mehrgitterverfahren) in eine iterative Lösung umwandeln?
Man kann zwar vermutlich in modernen Sprachen zu jedem rekursiv lösbaren Problem eine pseudo-iterative Lösung aufbauen, indem man sich z. B. einen Stack oder eine andere Datenstruktur aufbaut und iterativ befüllt bzw. leert, aber dann tritt wiederum die Frage auf, welche Schleifen die entsprechende Programmiersprache erlaubt und ob die iterative Lösung nicht unnötig kompliziert ist.
Aber das geht sicherlich über den AuD-Stoff hinaus.
Quatsch. Jede µ-rekursive (und auch jede λ-rekursive) Funktion kann beweisbar von einer Turing-Maschine berechnet werden. Und, um auch ein „reales“ Beispiel zu nennen: Fortran 77 kann keine Rekursion, ist aber turing-vollständig, und erlaubt es damit, jede berechenbare rekursive Funktion, die du dir ausdenken kannst, zu formulieren.
(Das Ganze hat aber herzlich wenig mit AuD zu tun. 
)
Danke für die Erklärung. Ich habe leider noch keine Vorlesungen zur theoretischen Informatik belegt, weshalb ich die µ- und λ-Rekursion nicht kenne, aber ich kann mir schon gut vorstellen, dass das so stimmt.
Bei Fortran 77 werde ich mir noch später den Beweis zur Turing-Vollständigkeit anschauen, wenn ich mal Zeit haben werde. Da gab es ja meines Wissens schon einige kontroverse Diskussionen.
a
???
@CodeMonkey, @kopan ich habe die Schleife so gemacht, dass sie von letzten bis i==0 Element läuft und vergleicht die Zeile i mit Zeile i-1, damit ich kein Zugriff auf Element auf index -1 versuche. Und hab Abbruchsfall if i==0 packeNicht, aber funktionier nicht. Ich weiß, dass diese Basisfall nicht gut ist, aber weiss nicht was passieren muss wenn ich auf die 0-te Zeile ankomme, weil wenn ich kein Abbruchsfall für i=0, dann wird auf index -1 zugegriffen? Was muss anders sein für die erste Element-muss nicht gepackt sein?
Danke euch.
Natürlich darfst du für i==0 nicht auf die vorherige Zeile zugreifen, aber wenn du mal genauer drüber nachdenkst, dann ist das auch gar nicht notwendig.
Vielleicht hilft dir folgendes Beispiel:
Stell dir vor ich gebe dir einen Rucksack mit einer Größe x und einen einzigen Gegenstand mit einer Größe y. Überlege dir (völlig unabhängig von irgendwelchen anderen Parametern), wann du diesen einzigen Gegenstand einpacken kannst und wann eben nicht.
Ich muss gucken ob die Größe der Gegenstand nicht die Größe der Rücksack überschreitet. Habe ich gemacht, aber immer noch funktioniert nicht?
Nimm den Code raus, sonst wirst du morgen des Plagiats beschuldigt ;).
Ansonsten geht es doch sowieso um den Abschnitt i==0 und deine Schleife läuft ja nur bis i > 0. D.h. diesen letzten Spezialfall i==0 musst du halt auch noch entsprechend handhaben.
Oki, danke schön, ich gucke noch mal 
Ich hab auch eine Frage dazu:
Beschreibt “startgroesse” die größe des Rucksacks?