58
правок
Изменения
→Метод динамического программирования
Если не нужно востанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.
Сложность алгоритма <tex>O(NW^2)</tex>.
