Изменения

==Ограниченый рюкзак =='''Ограниченый рюкзак''' (англ. ''Bounded 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> x_i \in (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(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>.  ==Не ограниченый ограниченный рюкзак =='''Не ограниченный рюкзак'''' (англ. "Unbounded 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> x_i \in (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(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>. ==Непрерывный рюкзак==""Непрерывный рюкзак "" (англ. "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> x_i \in (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(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>.