58
правок
Изменения
→Не ограниченный рюкзак
==Не ограниченный рюкзак==
'''Не ограниченный рюкзак''' (англ.''Unbounded Knapsack Proble'') - обобщение ограниченого рюкзака, в котором любой предмет может быть выбран любое количество раз.
'''Пример:''' перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товара на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
\end{cases}
</tex>
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.
Если не нужно востанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного, и использовать формулу:
<tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex>
Сложность алгоритма <tex>O(NW)</tex>.
