Sonstige Aufgaben Rückwärtsrekursion - Rucksackproblem

Kiwi1979

Kiwi1979

Hochschulabschluss
Master of Science
Hallo zusammen,

kann mir jemand erläutern, was hier mit der Rucksackfunktion F(k,y) geprüft wird? Ich kann zwar die Tabelle ganz gut füllen und komme auch auf das korrekte Ergebnis, verstehe aber - wenn ich mir alte Aufgaben anschaue - leider gar nicht, wie diese Funktion gefüllt wird...

Viele Grüße
Kiwi
 
Hallo Kiwi,

ich habe auch etwas länger gebraucht, bis ich dahinterkam. Was habe ich früher bloß ohne Internet gemacht? Achtung, es wird eine wortreiche Erklärung anhand der Aufgabe auf S. 73f :paperbag:

Mit Hilfe der Funktion F(k,y) kann man ermitteln, wie der Rucksack zu befüllen ist. Wir beginnen mit der Tabellen F unten rechts mit dem Wert 25, der an Position k=5 und y=10 steht und den maximalen Wert darstellt. Jetzt wechseln wir auf Tabelle j und suchen den Wert an der Position J(5,10), d.h. wir übernehmen die eben ermittelten k und y. Da steht eine 4, d.h. wir packen ein Element x4 ein.

Als nächstes berechnen wir das neue b. Unser aktuelles b = y = 10 und n = k = 5, da wir am Anfang der Rekursion stehen.
b = b - a_j(n,b) --> j(n,b) mit n=5 und b = 10 ergibt 4 (so wie wir das eben aus der Tabelle abgelesen haben). Damit suchen wir a4 und das ist der Koeffizient vor x4 in der Nebenbedingung, also 2. Daraus folgt unser neues b = 10 - 2 = 8, n bleibt 5.

Wir schauen uns an, was wir in Tabelle j an der Position j(5,8) finden: wieder eine 4, also packen wir das nächste Element x4 ein und berechnen das neue b. Das machen wir so oft bis b = 0 ist. In diesem Fall finden wir nur 4er, also packen wir nur x4-Elemente ein und zwar 5 Stück.

Ich hoffe, das war halbwegs verständlich :winken:
 
Hey Kiomi,

vielen Dank für deine Erklärung :thumbsup:. Ich befürchte nur ich hänge schon viel früher.... Du Beginnst ja bereits mit der Prüfung von b. Ich hänge aber bei dem Einsetzen in die Funktion F(k,y). Die Tabellen zu füllen stellt kein Problem dar, da man hier recht logisch vorgehen kann. Ich befürchte nur, dass der Lehrstuhl gerne immer die Prüfung anhand der o.g. Funktion sehen möchte und da verstehe ich die Vorgehensweise rein gar nicht... :-(

Viele Grüße
 
Ich verstehe leider nicht, was Du mit dem Einsetzen meinst. Das Einsetzen in F (k,y) kommt beim Aufbau der Tabelle vor. Ist es das bei Schritt 2 des Algorithmus?
 
Hast du das Skript von Pinkas? Dann könnte ich es anhand einer Aufgabe mal genauer definieren...
 
Nein, habe ich nicht. Sorry :-(
 
Nicht schlimm. Werde mich morgen noch mal reinknien und dann hier auch mal ein Beispiel hinterlassen... Sofern es reicht immer nur die Tabelle hinzuschreiben und nicht jedesmal noch die Prüfung zu erörtern wäre das Problem ja schon gelöst. Ich denke aber, dass Letzteres verlangt wird...
 
Ich komme an den Anhang nicht dran, weil ich keinen Account mehr habe.

Ich versuche es mir herzuleiten. Es ist die Prüfung aus Schritt 2 im Algorithmus. Wenn an der nächsten Position ein größerer Wert erreicht wird, wird dieser eingetragen. Hier erfolgt die Prüfung, anders herum, also, wenn der Wert an der vorhergehenden Position F (k-1,y) größer als F (k,y-ak) +ck, dann wurde kein größerer Wert erreicht und der Wert der vorhergehenden Position eingetragen (Schritt 3).

Das ist Teil des Aufbaus der Tabelle. Da Du den Aufbau so hinbekommst, brauchst Du die Formeln scheinbar nicht. Ich lese gerne bei Formeln nach :-D Gut, dass das Skript mit in die Klausur darf :whistling:
 
Ah jetzt ja - das Licht ist aufgegangen :ROFL: Ich muss mir die Formeln immer erst mal auf deutsch übersetzen....

Vielen Dank für deine Hilfe!!!
 
Hallo zusammen,

ich muss sagen, dass ich bei dem Thema Rucksackproblem absolut auf dem Schlauch stehe. Ich bin eher der Typ, der die ganzen Formeln erst versteht, wenn er sie für sich übersetzt hat und an einem plausiblen Beispiel nachvollziehen kann. Das ist beim Rucksackproblem auf Seite 70 für mich leider nicht der Fall, d.h. ich komme nicht mal darauf, wie man die Tabelle ordnungsgemäß befüllt. Vielleicht hat ja jemand hier schonmal das Beispiel 4.1 oder die entsprechende Übungsaufgabe 4.1 gerechnet und kann mir das irgendwie zur Verfügung stellen, das wäre eine riesige Hilfe für mich. Vielen Dank.

LG

Jörg
 
Hallo Jörg,

ich habe das Verfahren mal in Excel überführt und die entsprechenden Formeln eingetragen. Es gibt ein Blatt, in dem die Tabellen gefüllt werden und ein zweites, in dem die Lösung abgelesen wird. Vielleicht hilft Dir das beim Verständnis.
 

Anhänge

  • Kurs_00853_Beispiel_4_1.xlsx
    17 KB · Aufrufe: 118
Vielen Dank, damit hast du mir sehr geholfen!
LG Jörg
 
Hallo zusammen,

ich weiß hier gerade nicht weiter (Beispiel 4.1)
Ich habe:
y=7
k= 1
ak = 6
ck = 1

in Schritt 2 erhalte ist
F(0,7) >= F(1,1)+1

um F (k,y) zu erhalten muss ich ja nun den Term F(1,1)+ 1berechnen?
Rauskommen soll 1, wie komme ich hier jetzt auf die 1?
 
F (1,1) solltest Du in der Tabelle schon eingetragen haben. Der Wert ist 0 und 0+1=1 und dann hast Du es schon.
 
liegt die lösung dann eigtl immer in der letzten spalte der tabelle oder wie könnte das variieren?
 
Kiwi1979 schrieb:
Hier hat das auch schon mal jemand nett in eine Tabelle gebastelt

http://www.studienservice.de/thema/48608/

Aber ich komme einfach nicht darauf, was F(0,6) = 0 ≥ F(1,6-6) + c1 = 0 + 1 zu bedeuten hat
Zum Vergrößern anklicken....

Hey Kiwi,
könntest du den Anhang des anderen Forums hier noch mal reinstellen. Ich kann das nämlich leider nicht öffnben beim "studienservice".
Das wäre super nett!
Daaaaaanke + Lg.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben