40
правок
Изменения
м
Изменены знаки в неравенствах
Дано <tex>N</tex> предметов, <tex>W</tex> — вместимость рюкзака, <tex>w=\{w_{1},w_{2},...,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{N}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</tex> не включен, и такой что:
#<tex>b_{1} w_{1}+ ... + b_{N} w_{N} \le leqslant W</tex>
#<tex>b_{1} p_{1}+ ... + b_{N} p_{N} </tex> максимальна.
Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.
В первой строке как только вместимость рюкзака <tex>n \ge geqslant 3</tex>, добавляем в рюкзак 1 предмет.
Рассмотрим <tex>k = 3</tex>, при каждом <tex>s \ge geqslant 5 (</tex>так как <tex>w_3 = 5)</tex> сравниваем <tex>A[k-1][s]</tex> и <tex>A[k-1][s-w_3]+p_3</tex> и записываем в <tex>A[k][s]</tex> стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимости третьего предмета плюс стоимость рюкзака с вместимостью на <tex>w_3</tex> меньше.
Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>.
* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
* выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le leqslant W</tex>;
где <tex> x_i \in (0,1,...,b_i)</tex> для всех <tex> i= 1,2,...,N</tex>.
Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 1 до <tex>W</tex>, по рекуррентной формуле:
<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i) </tex> по всем целым <tex> l </tex> из промежутка <tex> 0 \le leqslant l \le leqslant min(b_i,\lfloor c/w_i \rfloor)</tex>.
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le leqslant W</tex>;
где <tex> x_i \ge geqslant 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.
===Варианты решения===
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le leqslant W</tex>;
где <tex> 0 \le leqslant x_i \le leqslant 1</tex> дробное, для всех <tex> i= 1,2,...,N</tex>.
===Варианты решения===
*максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_i</tex>;
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le leqslant W</tex>;
<tex> x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex>, для всех <tex> i= 1,2,...,N</tex>.
===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная сумма <tex>\le leqslant c</tex>, подмножества взятого из <tex> 1, ...,\ i</tex> элементов.
Заполним <tex>d(0,c)</tex> нулями.
*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;
Где <tex> x_i \ge geqslant 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.
===Варианты решения===
Самые распространенные методы точного решения это:
*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>;
*так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \le leqslant Wy_j \qquad j \in {1, ..., N}</tex>;
<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.
==Мультипликативный рюкзак==
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
'''Пример:''' У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
Максимизировать <tex>\sum_{i=1}^M \sum_{j=1}^{N} p_jx_{ij}</tex>
так, чтобы <tex>\sum_{i=1}^N w_jx_{ij} \le leqslant W_i</tex> выполнялось для всех <tex> i= 1,2,...,N</tex>.
<tex>\sum_{j=1}^{M}x_{ij}=1</tex> для всех <tex> i= 1,2,...,N</tex>.
==Задача о назначении==
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') — Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le leqslant 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> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
===Формулировка Задачи===
Максимизировать стоимость выбранных предметов <tex>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}</tex>,
при выполнении условия совместности <tex>\sum_{j=1}^N w_{ij} x_{ij} \le leqslant W_i \qquad i=1, \ldots, M</tex>.
<tex> \sum_{i=1}^M x_{ij} \leq 1 \qquad j=1, \ldots, N</tex>.
