Zunächst mal zu den Bezeichnungen
Rucksackproblem allgemein:
- Gegenstände 1,..,n
- jeweilige Mengen [tex]x_1,..,x_n[/tex]
- jeweilige Gewichte [tex]a_1,..,a_n[/tex]
- jeweiliger Nutzen [tex]c_1,..,c_n[/tex]
- Gesamtkapazität [tex]b[/tex]
Es kommen jetzt noch hinzu:
- Teilkapazitäten [tex]0 \le j \le b[/tex]
- Auswahl Gegenstände [tex]0 \le k \le n[/tex]
OK 😎
Was ist in der Tabelle für [tex]F(k,y)[/tex] dargestellt? => Der maximal erreichbare Gesamtnutzen (z) bei gegebenen y und k. Also: Welcher Gesamtnutzen ist für welche Teilkapazität mit welchen ausgewählten Gegenständen erreichbar.
Von praktischer Relevanz ist nur die letzte Spalte, da hier alle theoretisch möglichen Gegenstände einfließen. Die anderen Spalten werden nur für die rekursive Berechnung der Lösung benötigt.
Wie Du schon richtig erkannt hast, sind die Einträge für y=0 sowie k=0 sämtlich 0. Wo die einzelnen Gewichte größer sind als die Teilkapazitäten, also
[tex]y - a_k < 0[/tex],
kannst Du generell den Eintrag der Vorgänger-Spalte (jeweils links) übernehmen.
Alles weitere erledigen die Schritte 2. bis 4. Hier muss man sich nur stur an die jeweiligen Formeln und Einträge halten und möglichst sauber rechnen 🙄 Achtung, hoher Verkasper-Faktor 😀
Falls es da noch bei Dir haken sollte, können wir auch noch gemeinsam ein Beispiel durchgehen...
Was ist in der Tabelle für [tex]j(k,y)[/tex] dargestellt? => Der größte Index einer positiven Variablen in der Lösung.
Die Berechnung der Einträge erfolgt parallel zu den Einträgen der anderen Tabelle...
Wenn Du irgendwann die Tabellen komplett und fehlerfrei durchgerechnet hast, können wir die optimale Lösung schrittweise aus den Tabellen ermitteln.
Für den Zielfunktionswert ergibt sich:
[tex]z = F(5,10) = 25[/tex]
Die Gewichte der einzelnen Gegenstände ermitteln wir sukzessive:
Vorab:
[tex]x_1 = x_2 = x_3 = x_ 4 = x_5 = 0[/tex]
Aktuell verbleibende Kapazität (Gesamtkapazität]:
[tex]b = 10[/tex]
Höchster Index einer Variablen für y=b=10 ist 4 - siehe j(10,5):
[tex]x_4 = x_4 + 1 = 1[/tex]
Restkapazität ermitteln:
[tex]b = b - a_4 = 10 - 2 = 8[/tex]
Höchster Index einer Variablen für y=b=8 ist 4 - siehe j(8,5):
[tex]x_4 = x_4 + 1 = 2[/tex]
Restkapazität ermitteln:
[tex]b = b - a_4 = 8 - 2 = 6[/tex]
Höchster Index einer Variablen für y=b=6 ist 4 - siehe j(6,5):
[tex]x_4 = x_4 + 1 = 3[/tex]
Restkapazität ermitteln:
[tex]b = b - a_4 = 6 - 2 = 4[/tex]
Höchster Index einer Variablen für y=b=4 ist 4 - siehe j(4,5):
[tex]x_4 = x_4 + 1 = 4[/tex]
Restkapazität ermitteln:
[tex]b = b - a_4 = 4 - 2 = 2[/tex]
Höchster Index einer Variablen für y=b=2 ist 4 - siehe j(2,5):
[tex]x_4 = x_4 + 1 = 5[/tex]
Restkapazität ermitteln:
[tex]b = b - a_4 = 2 - 2 = 0[/tex]
=> Der Algorithmus terminiert!
Optimale Lösung:
[tex]x_1 = x_2 = x_3 = x_5 = 0, \quad x_4 = 5[/tex]
