Задача о рюкзаке

Турист собирает рюкзак: каждый предмет весит сколько-то и стоит сколько-то, вместимость конечна, цель — максимум суммарной ценности. Задача о рюкзаке в 0-1-варианте: предмет берётся целиком или не берётся вовсе; существует ещё дробный вариант, где можно отрезать кусок, но целые предметы встречаются на практике чаще. Прямой перебор — это перебор сочетаний всех объёмов: при n предметах подмножеств $2^n$, и уже при n = 30 вариант «всё перебрать» недоступен. Задача NP-трудна: полиномиального алгоритма для худшего случая не известно, и пределы, которые изучает сложность алгоритмов, здесь не абстракция, а рабочий потолок. Жадная эвристика «бери самое ценное на килограмм» интуитивна, но гарантий не даёт — в отличие от жадных алгоритмов на графах вроде алгоритма Краскала, где жадность доказуемо оптимальна.

Инстанс: вместимость 10, предметы (вес, ценность) — A(7,42), B(4,12), C(3,10), D(5,25). Подмножеств всего 2^4 = 16, перебор даёт оптимум A+C: вес ровно 10, ценность 42+10 = 52; ближайшие конкуренты D+B = 37 и C+D = 35. Таблица ДП ведёт W(i, w) — лучшую ценность на первых i предметах при вместимости w — и заполняет 4×11 клеток. Жадность по плотности ценности на вес здесь сначала берёт A (плотность 6,0), затем D не влезает, влезает C — снова 52, совпадение с оптимумом. Но это везение, а не закономерность: при вместимости 11 тот же жадный код опять даёт 52, тогда как оптимальный набор A+B стоит 54 при весе ровно 11 — жадность пропустила B ради более плотной C. Мораль: точность ДП покупается таблицей, скорость жадности — ошибками на неудобных данных. Восстановить состав набора помогает обратный проход по таблице: значения клеток подсказывают, брался ли предмет.