https://www.youtube.com/watch?v=8LusJS5-AGo

Задача о рюкзаке (англ. Knapsack problem) — дано N предметов, n_i предмет имеет массу wi>0 и стоимость pi>0. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины W (вместимость рюкзака), а суммарная стоимость была максимальна.

Метод динамического программирование всё равно не позволяет решать задачу за полиномиальное время, потому что его сложность зависит от максимального веса. Задача о ранце (или задача о рюкзаке) — одна из NP-полных задач комбинаторной оптимизации.