Math
Plecak: zachłanność kontra tabela
Wybierz ponumerowane ładunki przy limicie masy. Porównaj z zachłannym i optimum, otwórz komórkę tabeli i wróć do optymalnego wyboru.
Co się dzieje
Wybierz ponumerowane ładunki przy limicie masy. Porównaj z zachłannym i optimum, otwórz komórkę tabeli i wróć do optymalnego wyboru. T(i,c): najlepsza wartość pierwszych i przedmiotów przy pojemności c. Kliknij komórkę: niebieski pomija, zielony bierze. Strzałki przewijają tabelę. w = masa, v = wartość. Rozmiar jest dekoracyjny; ograniczona jest tylko suma mas. Granica ułamkowa pozwala dzielić przedmioty. To górna granica, a nie dopuszczalny wybór 0/1.
Równania modułu
Równania
0/1: sum(w_i x_i) <= W; max sum(v_i x_i), x_i należy do {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
