58
правок
Изменения
м
→Другие задачи семейства
===Варианты решения===
Изменение формулировки значительно облегчает задачу. Жадный алгоритм дает оптимальное решение в данном случае.
==Задача о суммах подмножеств==
'''Задача о суммах подмножеств'''' (англ. "Subset-sum problem, Value Independent Knapsack Problem") - задача из семейства, в которой стоимость предмета совпадает с его весом.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <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 \ge 0 </math> целое, для всех <math> i= 1,2,...,N</math>
===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ
* Метод динамического программирования
===Метод динамического программирования===
Пусть <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) =
\begin{cases}
d(i,c) = d(i - 1, c) & for\ c = 0, ..., w_i; \\
d(i,c) = max(d(i - 1, c), d(i, c - w_i) + p_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>
Если не нужно востанавливать ответ, то можно использовать одномерный массив <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)</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 \ge 0 </math> целое, для всех <math> i= 1,2,...,N</math>
===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ
* Метод динамического программирования
===Метод динамического программирования===
Пусть <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) =
\begin{cases}
d(i,c) = d(i - 1, c) & for\ c = 0, ..., w_i; \\
d(i,c) = max(d(i - 1, c), d(i, c - w_i) + p_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>
Если не нужно востанавливать ответ, то можно использовать одномерный массив <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)</tex>.
= Литература =
