S
StudiWS20092010
ich habe da eine Frage zum rekursiven Verfahren zur Lösung des Rucksackproblems (S.72 bis 73, Kurs "Ganzzahlige Optimierung):
Mir ist klar, dass bei F(k/y) sich das k auf den jeweiligen Koeffizienten bezieht, während das y Bezug auf die Kapazität nimmt. So bedeutet ja F(3/2), dass von x3 in dem Fall 3ME in den Rucksack gepackt werden.
Allerdings sind mir die folgenden Dinge an dem Verfahren nicht ganz klar:
1.) Bei Punkt 2 steht F(k-1,y) > F(k,y-ak)+ck. Wenn ich nun Bezug auf das Beispiel 4.2 (S.72) nehme und für den Koeffizienten sagen wir mal x3 entscheide, wovon ich 3 ME in den Rucksack einpacken möchte, dann heißt das ja
F(3-1,3)>F(3,3-4)+2? Ist das erst einmal so richtig? Meine sich daran anschließende Frage ist, wie nun das ck hinter der Klammer in den Term eingebaut werden soll. Meine Vermutung ist F (2,3) >F(3,-1+2) bzw. F(3,1)
2.) Meine zweite Frage ist:
Kann mir jemand am Beispiel eines Wertes, sagen wir mal F(4/7) erklären, wie der in der Tabelle F(k/y) und in der Tabelle j(k/y) eingetragene Wert von 15 bei F(4/7) und von 4 bei j(4/7) zustande kommt?
Ich danke im Voraus.
Mir ist klar, dass bei F(k/y) sich das k auf den jeweiligen Koeffizienten bezieht, während das y Bezug auf die Kapazität nimmt. So bedeutet ja F(3/2), dass von x3 in dem Fall 3ME in den Rucksack gepackt werden.
Allerdings sind mir die folgenden Dinge an dem Verfahren nicht ganz klar:
1.) Bei Punkt 2 steht F(k-1,y) > F(k,y-ak)+ck. Wenn ich nun Bezug auf das Beispiel 4.2 (S.72) nehme und für den Koeffizienten sagen wir mal x3 entscheide, wovon ich 3 ME in den Rucksack einpacken möchte, dann heißt das ja
F(3-1,3)>F(3,3-4)+2? Ist das erst einmal so richtig? Meine sich daran anschließende Frage ist, wie nun das ck hinter der Klammer in den Term eingebaut werden soll. Meine Vermutung ist F (2,3) >F(3,-1+2) bzw. F(3,1)
2.) Meine zweite Frage ist:
Kann mir jemand am Beispiel eines Wertes, sagen wir mal F(4/7) erklären, wie der in der Tabelle F(k/y) und in der Tabelle j(k/y) eingetragene Wert von 15 bei F(4/7) und von 4 bei j(4/7) zustande kommt?
Ich danke im Voraus.
