Как понять, что проблема с рюкзаком является NP-полной?
Мы знаем, что проблема ранцев может быть решена в O (nW) сложности с помощью динамического программирования. Но мы говорим, что это NP-полная проблема. Я чувствую, что это трудно понять здесь.
(n - количество предметов. W - максимальная громкость.)