==Непрерывный рюкзак==
""Непрерывный рюкзак"" (англ. "Continuous knapsack problem") -обобщение классической вариант задачи, когда любой предмет может быть взят некоторое количество разв котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
===Формулировка Задачи===
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.Задача выбрать число часть <tex>x_i</tex> предметов каждого типа предмета так, чтобы
максимизировать общую стоимость: <math>\sum_{i=1}^N p_ix_i</math>
выполнялось условие на совместность: <math>\sum_{i=1}^N w_ix_i \le W</math>
и <math> 0 \le x_i \in (0,le 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(0,c)</tex> нулями. Тогда меняя i от 1 до <tex>N</tex>, расчитаем на каждом шаге <tex>c</tex> от 0 до <tex>W</tex> по рекурентной формуле: <tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i : l\ integer</tex> <math>0 \le l \le min(b_i,\lfloor c/w_i \rfloor))</math> Если не нужно востанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного. Сложность алгоритма <tex>O(NW^2)</tex>Жадный алгоритм дает оптимальное решение в данном случае.
= Литература =
