58
правок
Изменения
→Другие задачи семейства
Задача выбрать число <tex>x_i</tex> предметов каждого типа так, чтобы
* максимизировать общую стоимость: <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>;
===Варианты решения===
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.
=== Реализация ===
for i = 0..W // база
for l = min(b[i], c / w[i]) .. 1 // ищем l для которого выполняется максимум
d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l);
Сложность алгоритма <tex>O(NW^2)</tex>.
==Неограниченный рюкзак==
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы
*максимизировать общую стоимость: <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(c)</tex> вместо двумерного, и использовать формулу:
<tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex>;
Задача выбрать часть <tex>x_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>;
===Варианты решения===
for i = 1..N // идем по предметам
if W >= w[i] //если помещается - берем
W -= w[i];
else
Нужно выбрать подмножество так, чтобы сумма ближе всего к <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_i \ge x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>;
===Варианты решения===
Для решения пригодны любые методы для классической задачи, однако , специализированые алгоритмы, обычно более оптимальны по параметрам. Используется:
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по дереву. Существуют алгоритмы основанные на этом методе со сложностью В худшем случае работают за <tex>minO(2\log_{10}max(w_j), 0.7n) </tex> и <tex>min(2,5\log_{10}(max(w_j), 0.8nn)</tex>.
===Метод динамического программирования===
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы
*минимизировать количество взятых предметов: <tex>\sum_{i=1}^N x_i</tex>;
*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;
Где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>;
===Варианты решения===
Самые распространенные методы точного решения это:
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') - имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.
'''Пример:''' нужно Нужно вывезти из шахты все куски руды, используя наименьшее количество вагонеток.
===Формулировка Задачи===
Математически задачу можно представить так:
*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>;
*так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \le Wy_j \qquad j \in {1, ..., N}</tex>;
<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.
<tex> y_i = 1 </tex> если <tex> i</tex> рюкзак используется. Иначе <tex> y_i = 0 </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> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
Весьма важная задача, так как она моделирует оптимальное распределение различных задач, между вычислительными блоками.
===Формулировка Задачи===
===Варианты решения===
Применение Динамического динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ (depth first branch and bound algorithm).
= Литература =
