==Ограниченый рюкзак ==
'''Ограниченый рюкзак''' (англ. ''Bounded Knapsack Problem'') - обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.
'''Пример:''' Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.
Сложность алгоритма <tex>O(NW^2)</tex>.
=== Реализация ===
Сначала генерируем <tex>A</tex>. for i = 0..W// база Ad[0][i] = 0 for i = 0..N A[i][0] = 0 //Первые элементы приравниваем 0 for k = 1..N for s c = 0..W //Перебираем для каждого ki, все вместисмости if s >= wd[k] //Если текущий предмет вмещается в рюкзак A[ki][sc] = max(Ad[ki -1][sc], A for l = min(b[k-1i][s-, c / w[k]]+p[ki]) .. 1 //выбираем класть его или нет else ищем l для которого выполняется максимум A d[ki][sc] = A[k-1][s] //иначе, не кладем Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией: findAnsmax(k, s) if Ad[ki][sc] == 0 return if A, d[ki -1][s] == Ac - l * w[ki][s] findAns(k-1, s) else findAns(k-1, s - w+ p[ki]* l); ans.push(k);
==Не ограниченный рюкзак==
