58
правок
Изменения
→Другие задачи семейства
* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
* выполнялось условие на совместностьсовместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;
где <tex> x_i \in (0,1,...,b_i)</tex> для всех <tex> i= 1,2,...,N</tex>;
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Proble'') - обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
'''Пример:''' перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товара товар на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
*выполнялось условие на совместностьсовместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;
где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>;
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного, и использовать формулу:
<tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex>;
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
*выполнялось условие на совместностьсовместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;
где <tex> 0 \le x_i \le 1</tex> дробное, для всех <tex> i= 1,2,...,N</tex>;
'''Пример:''' В машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
===Формулировка Задачи===
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Более формальноФормально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы
*максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_i</tex>;
*выполнялось условие на совместностьсовместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;
<tex> x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex>, для всех <tex> i= 1,2,...,N</tex>;
===Варианты решения===
Для решения пригодны любые методы применяемые для классической задачи, однако, специализированые алгоритмы, обычно более оптимальны по параметрам. Используется:
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по дереву. В худшем случае работают , работает за <tex> O(n) </tex>.
===Метод динамического программирования===
==Задача о размене==
'''Задача о размене''' (англ. ''Change-Making problem'') - имеются <tex> N </tex> не исчерпаемых неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>.
Часто задачу ставят как, дать сдачу наименьшим количеством монет.
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного, и использовать формулу:
<tex> d(c) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, ..., W </tex>;
===Варианты решения===
Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы , либо используют метод ветвей и границ.
==Мультипликативный рюкзак==
==Задача о назначении==
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') - Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики, в зависимости от рюкзака , куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>, у <tex> j </tex> предмета <tex> p_{ij} </tex> стоимость и вес, при помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответственно. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
===Формулировка Задачи===
