58
правок
Изменения
→Другие задачи семейства: сумма подмножества
Сложность алгоритма <tex>O(NW^2)</tex>.
==Не ограниченный рюкзак==
d(i,c) =
\begin{cases}
\end{cases}
</tex>
Сложность алгоритма <tex>O(NW)</tex>.
==Непрерывный рюкзак==
===Варианты решения===
Изменение формулировки значительно облегчает задачу. Жадный алгоритм дает оптимальное решение в данном случае.
==Задача о суммах подмножеств==
'''Задача о суммах подмножеств'''' (англ. "Subset-sum problem, Value Independent Knapsack Problem") - задача из семейства, в которой стоимость предмета совпадает с его весом.
===Формулировка Задачи===
максимизировать общую стоимость: <math>\sum_{i=1}^N p_ix_iw_ix_i</math>
выполнялось условие на совместность: <math>\sum_{i=1}^N w_ix_i \le W</math>
===Варианты решения===
* Метод динамического программирования
* Гибридный метод на основе динамического программирования и поиска по дереву. <math> O(n) </math> в худшем случае.
===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого количества вещей типов от 1 до сумма <tex>i\le c</tex>, суммарным весом до подмножества взятого из <tex>c1, ...,\ i</tex> включительно элементов.
Заполним <tex>d(0,c)</tex> нулями.
d(i,c) =
\begin{cases}
\end{cases}
</tex>
Сложность алгоритма <tex>O(NW)</tex>.
выполнялось условие на совместность: <math>\sum_{i=1}^N w_ix_i \le W</math>
<math> x_i \ge in {0 ,1} </math> целое, для всех <math> i= 1,2,...,N</math>
===Варианты решения===
d(i,c) =
\begin{cases}
\end{cases}
</tex>
