Изменения

Перейти к: навигация, поиск

Задача о рюкзаке

638 байт добавлено, 01:50, 5 июня 2017
Исправлен всевдокод. Заменены max. Исправлена плохочитаемый текст. Добавлено см. И т. д.
{{Задача
|definition =
'''Задача о рюкзаке'''(''англ. Knapsack problem'') — дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.
}}
== Формулировка задачи ==
Дано <tex>N</tex> предметов, <tex>W</tex> — вместимость рюкзака, <tex>w=\{w_{1},w_{2},...\dots,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...\dots,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин <tex>B=\{b_{1},b_{2},...\dots,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}+ ... \dots + b_{N} w_{N} \leqslant W</tex>#<tex>b_{1} p_{1}+ ... \dots + b_{N} p_{N} </tex> максимальна.
== Варианты решения ==
* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.
* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}\times*{N}) </tex>
* Метод динамического программирования. Сложность — <tex>O(N \times *W)</tex>.
== Метод динамического программирования ==
Пусть <tex>A(k, s)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,...\dots,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>.
<tex>A(k, 0) = 0</tex>
Найдем <tex>A(k, s)</tex>. Возможны 2 варианта:
#Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...\dots,n_{k-1}\}</tex>, то есть <tex>A(k,s) = A(k-1, s)</tex># Если <tex>k</tex> попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака, где вес <tex>s</tex> уменьшаем на вес <tex>k</tex>-ого предмета и набор допустимых предметов <tex>\{n_1,n_2,...\dots,n_{k-1}\}</tex> плюс стоимость <tex>k</tex>, то есть <tex>A(k-1, s-w_k) + p_k</tex>
<tex>
То есть:
<tex>A(k,s) = \max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})</tex>
Стоимость искомого набора равна <tex>A(N,W)</tex>, так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака <tex>W</tex>.
Будем определять, входит ли <tex>n_i</tex> предмет в искомый набор. Начинаем с элемента <tex>A(i,w)</tex>, где <tex>i = N</tex>, <tex>w = W</tex>. Для этого сравниваем <tex>A(i,w)</tex> со следующими значениями:
#Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...\dots,n_{i-1}\}</tex>, то есть <tex>A(i-1, w)</tex>#Максимальная стоимость рюкзака с вместимостью на <tex>w_i</tex> меньше и набором допустимых предметов <tex>\{n_1,n_2,...\dots,n_{i-1}\}</tex> плюс стоимость <tex>p_i</tex>, то есть <tex>A(i-1, w-w_i)+p_i</tex>
Заметим, что при построении <tex>A</tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w)</tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит.
Сначала генерируем <tex>A</tex>.
'''for''' i = 0..to W A[0][i] = 0; '''for''' i = 0..to N A[i][0] = 0; ''<font color="green">// Первые элементы приравниваем к 0</font>'' '''for''' k = 1..to N '''for''' s = 1..to W ''<font color="green">//Перебираем для каждого k все вместимости</font>'' '''if''' s >= w[k] ''<font color="green">//Если текущий предмет вмещается в рюкзак</font>'' A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]); ''<font color="green">//выбираем класть его или нет</font>''
'''else'''
A[k][s] = A[k-1][s]; ''<font color="green">//иначе, не кладем</font>''
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
findAns(k, s)
'''if''' A[k][s] == 0
'''return''';
'''if''' A[k-1][s] == A[k][s]
findAns(k-1, s);
'''else'''
findAns(k-1, s - w[k]); ans.push(k);
Сложность алгоритма <tex>O(N \times *W)</tex>
== Пример ==
'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''
Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ. Будем идти в обратном порядке по <tex>k</tex>. ''<font color="yellowred">Жёлтым Красным обозначен наш путь</font>''
{|border="1" class="wikitable" style="text-align:center" width="75%"
| k = 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0
|-
| k = 1 || 0 ||style="background:#FFFF00FF0000"| 0 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1
|-
| k = 2 || 0 || 0 || 1 || 6 ||style="background:#FFFF00FF0000"| 6 || 6 || 7 || 7 || 7 || 7 || 7 || 7 || 7
|-
| k = 3 || 0 || 0 || 1 || 6 ||style="background:#FFFF00FF0000"| 6 || 6 || 7 || 7 || 10 || 10 || 10 || 11 || 11
|-
| k = 4 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 13 ||style="background:#FFFF00FF0000"| 13
|-
| k = 5 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 13 ||style="background:#FFFF00FF0000"| 13
|}
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.
'''Пример:''' {{Задача|definition =Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.}} 
===Формулировка Задачи===
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.
* выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant W</tex>;
где <tex> x_i \in (0,1,...\dots,b_i)</tex> для всех <tex> i= 1,2,...\dots,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 \leqslant l \leqslant min(b_i,\lfloor c/w_i \rfloor)</tex>.
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.
=== Реализация ===
'''for''' i = 0..to W ''<font color="green">// база</font>'' d[0][i] = 0; '''for''' i = 1..to N '''for''' c = 1..to W ''<font color="green">//Перебираем для каждого i, все вместимости </font>'' d[i][c] = d[i - 1][c]; '''for''' l = min(b[i], c / w[i]) .. to 1 ''<font color="green">//ищем l для которого выполняется максимум </font>'' d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l);
Сложность алгоритма <tex>O(NWN*W^2)</tex>.
==Неограниченный рюкзак==
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
'''Пример:''' {{Задача|definition =Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.}} 
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant W</tex>;
где <tex> x_i \geqslant 0 </tex> целое, для всех <tex> i= 1,2,...\dots,N</tex>.
===Варианты решения===
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ...\dots, w_i - 1; \\ \max(d(i - 1, c), d(i, c - w_i) + p_i) & for\ c = w_i, ...\dots, W;
\end{cases}
</tex>
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:
<tex> d(c) = \max(d(c), d(c - w_i) + p_i) </tex>;
Сложность алгоритма <tex>O(NW)</tex>.
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
'''Пример:''' {{Задача|definition =Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.}} 
===Формулировка Задачи===
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant W</tex>;
где <tex> 0 \leqslant x_i \leqslant 1</tex> дробное, для всех <tex> i= 1,2,...\dots,N</tex>.
===Варианты решения===
=== Реализация ===
sort(); ''<font color="green">// сортируем в порядке убывания удельной стоимости.</font>'' '''for''' i = 1..to N ''<font color="green">// идем по предметам </font>'' '''if''' W > w[i] ''<font color="green">//если помещается — берем</font>'' sum += p[i]; W -= w[i];
'''else'''
sum += W / w[i] * p[i]; ''<font color="green">// иначе берем сколько можно и выходим</font>'' '''break''';
==Задача о суммах подмножеств==
'''Задача о суммах подмножеств''' (англ. ''Subset—sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.
'''Пример:''' {{Задача|definition =Машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.}} 
===Формулировка Задачи===
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant W</tex>;
<tex> x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex>, для всех <tex> i= 1,2,...\dots,N</tex>.
===Варианты решения===
===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная сумма <tex>\leqslant c</tex>, подмножества взятого из <tex> 1, ...\dots,\ i</tex> элементов.
Заполним <tex>d(0,c)</tex> нулями.
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ...\dots, w_i - 1; \\ \max(d(i - 1, c), d(i - 1, c - w_i) + w_i) & for\ c = w_i, ...\dots, W;
\end{cases}
</tex>
==Задача о размене==
{{Задача
|definition =
'''Задача о размене''' (англ. ''Change-Making problem'') — имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>.
}}
Часто задачу ставят как, дать сдачу наименьшим количеством монет.
*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;
Где <tex> x_i \geqslant 0 </tex> целое, для всех <tex> i= 1,2,...\dots,N</tex>.
===Варианты решения===
Самые распространенные методы точного решения это:
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ...\dots, w_i - 1; \\ min(d(i - 1, c), d(i, c - w_i) + 1) & for\ c = w_i, ...\dots, W;
\end{cases}
</tex>
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:
<tex> d(c) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, ...\dots, W</tex>.
Сложность алгоритма <tex>O(NW)</tex>.
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') — имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.
'''Пример:''' {{Задача|definition =Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.}} 
===Формулировка Задачи===
Математически задачу можно представить так:
*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>;
*так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \leqslant Wy_j \qquad j \in {1, ...\dots, 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\leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
'''Пример:''' {{Задача|definition =У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.}} 
===Формулировка Задачи===
Максимизировать <tex>\sum_{i=1}^M \sum_{j=1}^{N} p_jx_{ij}</tex>
так, чтобы <tex>\sum_{i=1}^N w_jx_{ij} \leqslant W_i</tex> выполнялось для всех <tex> i= 1,2,...\dots,N</tex>.
<tex>\sum_{j=1}^{M}x_{ij}=1</tex> для всех <tex> i= 1,2,...\dots,N</tex>.
==Задача о назначении==
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') — Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\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> соответственно.  {{Задача: выбрать |definition =Выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.}}
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
===Формулировка Задачи===
===Варианты решения===
Применение динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ.
 
== См. также ==
* [[Класс NP]]
* [[Метод четырех русских для умножения матриц]]
* [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
== Источники информации ==
40
правок

Навигация