Задача о рюкзаке простыми словами — что это вообще за задача?
Постоянно всплывает «задача о рюкзаке» (knapsack) как пример динамического программирования. Можете объяснить на пальцах, в чём суть, и почему её нельзя решить простым жадным алгоритмом?
4 ответа
Суть: есть рюкзак с ограничением по весу W и набор предметов, у каждого свой вес и ценность. Надо набрать предметы с максимальной суммарной ценностью, не превысив W. В классической версии (0/1) каждый предмет либо берёшь целиком, либо нет.
Почему не жадность: жадный подход «бери самое ценное на единицу веса» для дробного рюкзака (можно брать части) работает, а для 0/1-рюкзака — нет. Контрпример: W=10, предметы (вес 6, цена 7), (вес 5, цена 5), (вес 5, цена 5). Жадность по «цене за вес» возьмёт первый (7), останется место на 4 — больше ничего не влезет, итог 7. А оптимум — два по 5: вес 10, цена 10.
Поэтому 0/1-рюкзак решают через ДП: таблица dp[i][w] = максимальная ценность из первых i предметов при лимите w. Сложность O(n*W).
Набрать предметов на максимум ценности, не перевесив рюкзак. 0/1-версию жадностью не решить, нужно ДП.
Жадностью не решается.
Бери всегда самый дорогой предмет, пока влезает — вот и решение.
