Math
Rucksack: Gier gegen die Tabelle
Wähle nummerierte Kisten unter einem Gewichtslimit. Vergleiche mit Gier und der exakten Lösung, öffne eine Tabellenzelle und verfolge die optimale Auswahl rückwärts.
Was passiert
Wähle nummerierte Kisten unter einem Gewichtslimit. Vergleiche mit Gier und der exakten Lösung, öffne eine Tabellenzelle und verfolge die optimale Auswahl rückwärts. T(i,c): bester Wert der ersten i Gegenstände bei Kapazität c. Klicke eine Zelle: Blau lässt aus, Grün nimmt. Pfeile blättern. w = Gewicht, v = Wert. Die Kistengröße ist dekorativ; nur das Gesamtgewicht zählt. Die teilbare Grenze gehört zu einer anderen Aufgabe mit teilbaren Gegenständen. Sie ist keine zulässige 0/1-Auswahl.
Gleichungen des Moduls
Gleichungen
0/1: sum(w_i x_i) <= W; max sum(v_i x_i), x_i aus {0,1}
T(0,c) = 0
w_i > c: T(i,c) = T(i-1,c)
w_i <= c: T(i,c) = max(T(i-1,c), v_i + T(i-1,c-w_i))
v_i/w_i ↓; i ↑
F_greedy <= F_0/1 <= F_fractional
V_single = max({0} ∪ {v_i : w_i <= W})
max(F_greedy, V_single) >= F_0/1 / 2
N_DP = n*W; N_subsets = 2^n
