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
