Изменения

'''Не ограниченный рюкзак'''' (англ. "Unbounded Knapsack Problem") - обобщение классической задачиограниченого рюкзака, когда в котором любой предмет может быть взят некоторое выбран любое количество раз.

Каждый предмет может быть выбран ограниченное <tex>b_i</tex> любое число раз.Задача выбрать число количество <tex>x_i</tex> предметов каждого типа так, чтобы

и <math> x_i \in (ge 0,1,...,b_i)</math> целое, для всех <math> i= 1,2,...,N</math>

При небольших <tex>b_i</tex> решается сведением к классической задаче о рюкзаке. В иных случаяхСамые распространенные методы точного решения это:* Методом Метод ветвей и границ* Методом Метод динамического программирования

Пусть <tex>d(i,c)</tex> максимальная стоимость любого возможного числа количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex>включительно .

<tex>d(i,c) = max\begin{cases} d(i,c) = d(i - 1, c - lw_i) + lp_i : l& for\ integer</tex> <math>c = 0 , ..., w_i; \le l \le min d(b_ii,c) = max(d(i - 1, c), d(i, c - w_i) + p_i) & for\lfloor c/= w_i , ..., W; \rfloor))end{cases}</mathtex>

Если не нужно востанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного., используя формулу:

<tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex> После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак. Сложность алгоритма <tex>O(NW^2)</tex>.