Math
Рюкзак: жадібність проти таблиці
Збери пронумеровані вантажі за обмеження маси. Порівняй із жадібним і точним рішенням, відкрий клітинку таблиці та пройди зворотний хід до оптимального набору.
Що відбувається
Збери пронумеровані вантажі за обмеження маси. Порівняй із жадібним і точним рішенням, відкрий клітинку таблиці та пройди зворотний хід до оптимального набору. T(i,c): найкраща цінність із перших i предметів за місткості c. Клацни клітинку: синій — пропустити, зелений — взяти. Стрілки гортають таблицю. w — маса, v — цінність. Розмір умовний; обмежена лише сума мас. Дробова межа стосується задачі, де предмети можна ділити. Це верхня межа, а не допустимий набір 0/1.
Рівняння модуля
Рівняння
0/1: sum(w_i x_i) <= W; max sum(v_i x_i), x_i із {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
