58
правок
Изменения
→Другие задачи семейства
Задача выбрать число <tex>x_i</tex> предметов каждого типа так, чтобы
максимизировать общую стоимость: <mathtex>\sum_{i=1}^N p_ix_i</mathtex>
выполнялось условие на совместность: <mathtex>\sum_{i=1}^N w_ix_i \le W</mathtex>
и <mathtex> x_i \in (0,1,...,b_i)</mathtex> для всех <mathtex> i= 1,2,...,N</mathtex>
===Варианты решения===
Тогда меняя i от 1 до <tex>N</tex>, расчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекурентной формуле:
<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i : l\ integer</tex> <mathtex>0 \le l \le min(b_i,\lfloor c/w_i \rfloor))</mathtex>
Если не нужно востанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы
максимизировать общую стоимость: <mathtex>\sum_{i=1}^N p_ix_i</mathtex>
выполнялось условие на совместность: <mathtex>\sum_{i=1}^N w_ix_i \le W</mathtex>
<mathtex> x_i \ge 0 </mathtex> целое, для всех <mathtex> i= 1,2,...,N</mathtex>
===Варианты решения===
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы
максимизировать общую стоимость: <mathtex>\sum_{i=1}^N p_ix_i</mathtex>
выполнялось условие на совместность: <mathtex>\sum_{i=1}^N w_ix_i \le W</mathtex>
<mathtex> 0 \le x_i \le 1</mathtex> дробное, для всех <mathtex> i= 1,2,...,N</mathtex>
===Варианты решения===
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Более формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы
максимизировать общую стоимость: <mathtex>\sum_{i=1}^N w_ix_i</mathtex>
выполнялось условие на совместность: <mathtex>\sum_{i=1}^N w_ix_i \le W</mathtex>
<mathtex> x_i \ge 0 </mathtex> целое, для всех <mathtex> i= 1,2,...,N</mathtex>
===Варианты решения===
Для решения пригодны любые методы для классической задачи, однако специализированые алгоритмы, обычно более оптимальны по параметрам. Используется:
* Метод динамического программирования
* Гибридный метод на основе динамического программирования и поиска по дереву. <mathtex> O(n) </mathtex> в худшем случае.
===Метод динамического программирования===
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы
минимизировать количество взятых предметов: <mathtex>\sum_{i=1}^N x_i</mathtex>
сумма весов выбранных предметов равнялась вместимости рюкзака: <mathtex>\sum_{i=1}^N w_ix_i = W</math> <math> x_i \ge 0 </math> целое, для всех <math> i= 1,2,...,N</mathtex>
<tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>
===Варианты решения===
Самые распространенные методы точного решения это:
Математически задачу можно представить так:
минимизировать количество рюкзаков: <mathtex>\sum_{i=1}^N y_i</mathtex>
так чтобы выполнялось условие на совместность:
<mathtex>\sum_{i=1}^N w_ix_{ij} \le Wy_j \qquad j \in {1, ..., N}</mathtex>
<tex>
==Мультипликативный рюкзак==
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') - есть <mathtex>N</mathtex> предметов и <mathtex>M</mathtex> рюкзаков (<mathtex>M\le N</mathtex>). У каждого рюкзака своя вместимость <mathtex>W_i</mathtex>. Задача: выбрать <mathtex>M</mathtex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
'''Пример:''' У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
===Формулировка Задачи===
максимизировать <mathtex>\sum_{i=1}^M \sum_{j=1}^{N} p_jx_{ij}</mathtex>
так чтобы <mathtex>\sum_{i=1}^N w_jx_{ij} \le W_i</mathtex> выполнялось для всех <mathtex> i= 1,2,...,N</mathtex>,
<mathtex>\sum_{j=1}^{M}x_{ij}=1</mathtex> для всех <mathtex> i= 1,2,...,N</mathtex>
<tex>
==Задача о назначении==
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') - Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики, в зависимости от рюкзака куда его помещают. Есть <mathtex>N</mathtex> предметов и <mathtex>M</mathtex> рюкзаков (<mathtex>M\le N</mathtex>). У каждого рюкзака своя вместимость <mathtex>W_i</mathtex>, у <tex> j </tex> предмета <tex> p_{ij} </tex> стоимость и вес,при помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответвенно. Задача: выбрать <mathtex>M</mathtex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
Весьма важная задача, так как она моделирует оптимальное распределение различных задач, между вычислительными блоками.
===Формулировка Задачи===
:максимизировать стоимость выбранных предметов <mathtex>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}.</mathtex>:при выполнении условия совместности <mathtex>\sum_{j=1}^N w_{ij} x_{ij} \le W_i \qquad i=1, \ldots, M</mathtex>;::<mathtex> \sum_{i=1}^M x_{ij} \leq 1 \qquad j=1, \ldots, N</mathtex>;::<mathtex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</mathtex>;
===Варианты решения===
