Изменения

Перейти к: навигация, поиск

Задача о рюкзаке

239 байт добавлено, 13:39, 11 января 2013
Не ограниченный рюкзак
==Не ограниченный рюкзак==
'''Не ограниченный рюкзак'''' (англ. "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 (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(0,c)</tex> нулями.
Тогда меняя i от 1 до <tex>N</tex>, расчитаем на каждом шаге <tex>c</tex> от 0 до <tex>W</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>.
==Непрерывный рюкзак==
58
правок

Навигация