Изменения

{{Задача|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} \le leqslant W</tex>#<tex>b_{1} p_{1}+ ... \dots + b_{N} p_{N} </tex> максимальна.

'''Задачу о рюкзаке можно решить несколькими способами:'''

* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}\times{N}) </tex>

* Метод динамического программирования. Сложность - — <tex>O(N \times WNW)</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>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>A(k,s) = \begin{cases} A(k-1, s)</tex>#<tex>A(k,s) & b_k = 0 \\ A(k-1, s-w_k) + p_k, & b_k = 1 \\\end{cases}</tex> Выберем из этих двух значений максимальное:

То есть: <tex>A(k,s) = \max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})</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>

'''for ''' i = 0..W'''to''' w

'''for ''' i = 0..N'''to''' n A[i][0] = 0 ''<font color="green">//Первые элементы приравниваем к 0</font>'' '''for ''' k = 1..N '''to''' n '''for ''' s = 0..W 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>''

'''function''' findAns('''int''' k, '''int''' 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 WNW)</tex>

{| classborder="wikitable1" cellpaddingclass="4wikitable" borderstyle="1text-align:center" stylewidth="border-collapse: collapse;75%"

| || 0! || 1|| 2|| 3|| 4|| 5|| 6|| 7|| 8|| 9 || 10 || 11 || 12 || 13

| k = 0 || 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0 || 0 || 0 || 0 || 0|| 0

| k = 1|| 0 || 0|| 0|| 1|| 1|| 1|| 1|| 1|| 1|| 1 || 1 || 1 || 1 || 1

| k = 2|| 0 || 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 7 || 7 || 7 || 7 || 7

| k = 3|| 0 || 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 10|| 10 || 10 || 11 || 11

| k = 4|| 0 || 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 10|| 10 || 10 || 13 || 13

| k = 5|| 0 || 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 10|| 10 || 10 || 13 || 13

В первой строке как только вместимость рюкзака <tex>n \ge geqslant 3</tex>, добавляем в рюкзак 1 предмет. [[Файл:Knapsack problem1.png]]

Рассмотрим <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>k</tex>. ''<font color="000000">Красным фоном обозначим наш путь</font>''

[[Файл{|border="1" class="wikitable" style="text-align:Knapsack problem2.png]]center" width="75%"|-! || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 |-| k = 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 |-| k = 1 || 0 ||style="background:#FF0000"| 0 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 |-| k = 2 || 0 || 0 || 1 || 6 ||style="background:#FF0000"| 6 || 6 || 7 || 7 || 7 || 7 || 7 || 7 || 7 |-| k = 3 || 0 || 0 || 1 || 6 ||style="background:#FF0000"| 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:#FF0000"| 13 |-| k = 5 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 13 ||style="background:#FF0000"| 13 |}

Стоимость рюкзака : <tex>= 6 + 7 = 13</tex>

Вес рюкзака : <tex>= 4 + 8 = 12</tex>

==Ограниченый Ограниченный рюкзак =={{Задача|definition ='''Ограниченый Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') - — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.}} 

* максимизировать общую стоимость: <mathtex>\sum_{i=1}^N p_ix_i</mathtex>;

* выполнялось условие на совместностьсовместности: <mathtex>\sum_{i=1}^N w_ix_i \le leqslant W</mathtex>;

и где <mathtex> x_i \in (0,1,...\dots,b_i)</mathtex> для всех <mathtex> i= 1,2,...\dots,N</mathtex>.

* Методом ветвей и границ.* Методом динамического программирования.

Тогда меняя i от 1 до <tex>N</tex>, расчитаем рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 1 до <tex>W</tex>, по рекурентной рекуррентной формуле:

<tex>d(i,c) = \max(d(i, c), d(i - 1, c - lw_i) + lp_i : ) </tex> по всем целым <tex> l\ integer</tex> из промежутка <mathtex>0 \le leqslant l \le leqslant min(b_i,\lfloor c/w_i \rfloor))</mathtex>.

Если не нужно востанавливать восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.

'''for ''' i = 0..W '''to''' w ''<font color="green">//База</ базаfont>''

'''for ''' i = 1..N '''to''' n '''for ''' c = 0..W 1 '''to''' w ''<font color="green">//Перебираем для каждого i, все вместисмости вместимости </font>''

'''for ''' l = min(b[i], c / w[i]) .. '''downto''' 1 ''<font color="green">// ищем Ищем l для которого выполняется максимум</font>''

Сложность алгоритма <tex>O(NW^2)</tex>.==Не ограниченный Неограниченный рюкзак=={{Задача|definition ='''Не ограниченный Неограниченный рюкзак''' (англ.''Unbounded Knapsack ProbleProblem'') - — обобщение ограниченого ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.}}

*максимизировать общую стоимость: <mathtex>\sum_{i=1}^N p_ix_i</mathtex>;

*выполнялось условие на совместностьсовместности: <mathtex>\sum_{i=1}^N w_ix_i \le leqslant W</mathtex>;

где <mathtex> x_i \ge geqslant 0 </mathtex> целое, для всех <mathtex> i= 1,2,...\dots,N</mathtex>.

* Метод ветвей и границ.* Метод динамического программирования.

Пусть <tex>d(i,c)</tex> - максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.

Тогда меняя i от 1 до <tex>N</tex>, расчитаем рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекурентной рекуррентной формуле:

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;

Если не нужно востанавливать восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного, и использовать формулу: <tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex> 

{{Задача|definition ='''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') - — вариант задачи, в котором возможно брать любою любую дробную часть от предмета, при этом удельная стоимость сохраняется.}}

*максимизировать общую стоимость: <mathtex>\sum_{i=1}^N p_ix_i</mathtex>;

*выполнялось условие на совместностьсовместности: <mathtex>\sum_{i=1}^N w_ix_i \le leqslant W</mathtex>;

где <mathtex> 0 \le leqslant x_i \le leqslant 1</mathtex> дробное, для всех <mathtex> i= 1,2,...\dots,N</mathtex>.

Изменение формулировки значительно облегчает Возможность брать любую часть от предмета сильно упрощает задачу. Жадный алгоритм дает оптимальное решение в данном случае.

sort() ''<font color="green">// сортируем Сортируем в порядке убывания удельной стоимости.</font>''  '''for ''' i = 1..N '''to''' n ''<font color="green">// идем Идем по предметам </font>'' '''if W ''' w > w[i] ''<font color="green">//если Если помещается - — берем</font>'' summ sum += p[i] W w -= w[i] '''else''' summ sum += W w / w[i] * p[i] ''<font color="green">// иначе Иначе берем сколько можно и выходим</font>'' exit '''break'''

{{Задача|definition ='''Задача о суммах подмножеств''' (англ. ''Subset-sum problem, Value Independent Knapsack Problem'') - — задача из семейства, в которой стоимость предмета совпадает с его весом.}}

Нужно выбрать подмножество так, чтобы сумма ближе всего к <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 leqslant W</mathtex>;

<mathtex> x_i \ge x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </mathtex> целое, для всех <mathtex> i= 1,2,...\dots,N</mathtex>.

Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы, обычно более оптимальны по параметрам. ИспользуетсяИспользуются:* Метод динамического программирования.* Гибридный метод на основе динамического программирования и поиска по деревуИспользовать различные сложные алгоритмы <ref>http://hjemmesider.diku.dk/~pisinger/codes.html</ref><ref>Pisinger D (1999). "Linear Time Algorithms for Knapsack Problems with Bounded Weights". ''Journal of Algorithms'', Volume 33, Number 1, October 1999, pp. 1–14</ref><mathref> OKoiliaris, Konstantinos; Xu, Chao (n2015-07-08) . "A Faster Pseudopolynomial Time Algorithm for Subset Sum".</ref><ref>Bringmann K. A near-linear pseudopolynomial time algorithm for subset sum[C]//Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2017: 1073-1084</mathref> в худшем случае.

Пусть <tex>d(i,c)</tex> максимальная сумма <tex>\le leqslant c</tex>, подмножества взятого из <tex> 1, ...\dots,\ i</tex> элементов.

Тогда меняя i от 1 до <tex>N</tex>, расчитаем рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекурентной рекуррентной формуле:

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;

{{Задача|definition ='''Задача о размене''' (англ. ''Change-Making problem'') - — имеются <tex> N </tex> не исчерпаемых неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</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>d(i,c)</tex> минимальное число премдетовпредметов, типов от 1 до <tex>i</tex>, необходимое, чтобы заполнить рюкзак вместимостью <tex>c</tex>.

Тогда меняя i от 1 до <tex>N</tex>, расчитаем рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекурентной рекуррентной формуле:

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;

Если не нужно востанавливать восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного, и использовать формулу:

<tex> d(c) = min(d(c), d(c - w_i) + 1) \ \ \ qquad for\ c = w_i, ...\dots, W </tex>.

{{Задача|definition ='''Задача об упаковке''' (англ. ''Bin Packing Problem'') - — имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.}} 

*минимизировать количество рюкзаков: <mathtex>\sum_{i=1}^N y_i</mathtex>; *так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \leqslant Wy_j \qquad j \in {1, \dots, N}</tex>;

так чтобы выполнялось условие на совместность: <mathtex>\sum_x_{iij} =1}^N w_ix_</tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} \le Wy_j \qquad j \in {1, ..., N}= 0 </mathtex>.

<tex>x_{ij}\begin{cases} y_i = 1 & \text{if j item is assigned to </tex> если <tex> i knapsack};\\ </tex> рюкзак используется. Иначе <tex> y_i = 0 & \text{else};\end{cases}</tex>.

Применение Динамического динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ.

{{Задача|definition ='''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') - — есть <mathtex>N</mathtex> предметов и <mathtex>M</mathtex> рюкзаков (<mathtex>M\le leqslant 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 leqslant W_i</mathtex> выполнялось для всех <mathtex> i= 1,2,...\dots,N</mathtex>,.

<mathtex>\sum_{j=1}^{M}x_{ij}=1</mathtex> для всех <mathtex> i= 1,2,...\dots,N</mathtex>.

 <tex>x_{ij}\begin{cases} = 1 & \text{if </tex> если <tex> j item is assigned to </tex> предмет назначен <tex>i knapsack</tex> рюкзаку. Иначе <tex> x_{ij};\\ = 0 & \text{else};\end{cases}</tex>.

Применение Динамического динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ.

{{Задача|definition ='''Задача о назначении''' (англ. ''Generalized Assignment Problem'') - — Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики, в зависимости от рюкзака , куда его помещают. Есть <mathtex>N</mathtex> предметов и <mathtex>M</mathtex> рюкзаков (<mathtex>M\le leqslant N</mathtex>). У каждого рюкзака своя вместимость <mathtex>W_i</mathtex>, у <tex> j </tex> предмета <tex> p_{ij} </tex> стоимость и вес,при помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответвенносоответственно. Задача: выбрать <math>M</math> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.}} Весьма важная задача, так как она моделирует оптимальное распределение различных задач, между вычислительными блоками.

:максимизировать Максимизировать стоимость выбранных предметов <mathtex>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}.</mathtex>, :при выполнении условия совместности <mathtex>\sum_{j=1}^N w_{ij} x_{ij} \le leqslant W_i \qquad i=1, \ldots, M</mathtex>;. ::<mathtex> \sum_{i=1}^M x_{ij} \leq leqslant 1 \qquad j=1, \ldots, N</mathtex>;. ::<mathtex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</mathtex>;.

Применение Динамического динамического программирования нецелесообразно.Наиболее используем метод ветвей и границ. == См. также ==* [[Класс NP]]* [[Метод четырех русских для умножения матриц]]* [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]* [[Meet-in-the-middle]]

= Литература = Источники информации ==

*Silvano Martello, Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations— 1990 г. Silvano Martello, Paolo Toth.— ISBN 0-471-92420-2