Изменения

{{Задача|definition ='''Задача о рюкзаке''' (''англ. Knapsack problem'') — дано <tex>kN</tex> предметов, i-й  <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.}}

Дано <tex>kN</tex> предметов, <tex>W</tex> - — вместимость рюкзака, <tex>w=\{w_{1},w_{2},...\dots,w_{kN}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...\dots,p_{kN}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно определить найти набор бинарных величин <tex>B=\{b_{1},b_{2},...\dots,b_{kN}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</tex> не включен, и такой что:

1. #<tex>b_{1} w_{1}+ ... \dots + b_{kN} w_{kN} \le leqslant W</tex>#<tex>b_{1} p_{1}+ \dots + b_{N} p_{N} </tex> максимальна.

1. Перебирая все подмножества набора из k предметов* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность такого решения <tex>O({2^{kN/2}}{N})</tex>.

2. Методом [http://neerc.ifmo.ru/wiki/index.php?title=Meet-in-the-middle#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D1.80.D1.8E.D0.BA.D0.B7.D0.B0.D0.BA.D0.B5 Meet-in-the-middle]* Метод динамического программирования. Сложность решения — <tex> O({2^{N/2}}\times{N}NW) </tex>.

3. == Метод динамического программирование. Сложность - <tex>O(k \times W)</tex>. Рассмотрим этот алгоритм подробнее.программирования ==

'''Алгоритм Пусть <tex>OA(k , s)</tex> есть максимальная стоимость предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,\dots,n_k\times W}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>'''.

Пусть <tex>A(sk, n0)= 0</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости n, если можно использовать только первые s предметов из заданных k.

<tex>A(0, s, 0) = 0</tex>

Найдем <tex>A(0k, ns) = 0</tex>. Возможны 2 варианта:

Найдем #Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1, nn_2,\dots,n_{k-1}\}</tex>, то есть <tex>A(k,s) = A(k-1, s)</tex># Если <tex>k</tex> попал в рюкзак. Возможны 2 варианта:Тогда <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>

1. Если предмет <tex>A(k, s</tex> не попал в рюкзак. Тогда <tex>) =\begin{cases} A(k-1, s), n) & b_k = 0 \\ A(sk-1, ns-w_k)+ p_k, & b_k = 1 \\\end{cases}</tex>

2. Если <tex>s</tex> попал в рюкзак. Тогда То есть: <tex>A(k,s, n) = \max(A(k-1,s), A(k-1, ns-w_{sk}) + p_{sk})</tex>

Таким образом:Стоимость искомого набора равна <tex>A(sN,n) = max(A(s-1,nW)</tex>, A(s-1так как нужно найти максимальную стоимость рюкзака,n-w_{s}) + p_{s})где все предметы допустимы и вместимость рюкзака <tex>W</tex>.

Теперь найдем '''Восстановим набор предметов, входящих в рюкзак.'''

Рассмотрим Будем определять, входит ли <tex>kn_i</tex> - последний предмет в рюкзакискомый набор. Если Начинаем с элемента <tex>A(ki,w)</tex>, где <tex>i = N</tex>, <tex>w = W)</tex> равно . Для этого сравниваем <tex>A(k-1i, Ww)</tex>, значит последний предмет не входит в набор, иначе входит. Так рекусривно идем до первого предмета. Получаем искомый набор.со следующими значениями:

Сложность алгоритма #Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов <tex>O\{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(kWi-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит. Метод динамического программирование всё равно не позволяет решать задачу за полиномиальное время, потому что его сложность зависит от максимального веса. Задача о ранце (или задача о рюкзаке) — одна из [[Класс NP|NP-полных]] задач комбинаторной оптимизации.

Сначала генерируем <tex>АA</tex>.

'''for (''' i = 0; i <= W; ++i)'''to''' w

'''for (''' i = 0; i <= k; ++i)'''to''' n A[i][0] = 0 { ''<font color="green">//Первые элементы приравниваем к 0}</font>'' '''for (s ''' k = 1; s <= k; ++s) '''to''' n '''for (n ''' s = 0; n 1 '''to''' w ''<font color= W; ++n) {"green">//Перебираем для каждого s, k все n}вместимости</font>'' '''if n ''' s >= w[sk] { ''<font color="green">//Если текущий предмет можно положить вмещается в рюкзак}</font>'' A[sk][ns] = max(A[sk -1][ns], A[sk -1][ns -w[sk]]+p[sk]) {выбираем ''<font color="green">//Выбираем класть его или нет}</font>'' '''else ''' A[sk][ns] = A[sk -1][ns] {иначе ''<font color="green">//Иначе, не кладем}</font>''

void '''function''' findAns('''int''' k, '''int''' s, n) '''if ''' A[sk][ns] == 0 '''return''' '''if ''' A[sk -1][ns] == A[sk][ns] findAns(sk -1, ns) '''else ''' findAns(sk -1, n s - w[sk]); ans.push(sk) Сложность алгоритма <tex>O(NW);</tex>

<tex>W = 1513, k N = 5</tex>  <tex>w_{1} = 3, p_{1} = 1 </tex> <tex>w_{2} = 4, p_{2} = 6 </tex> <tex>w_{3} = 5, p_{3} = 4 </tex> <tex>w_{4} = 8, p_{4} = 7 </tex> <tex>w_{5} = 9, p_{5} = 6 </tex>  {|border="1" class="wikitable" style="text-align: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 || 0 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 |-| k = 2 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 7 || 7 || 7 || 7 || 7 |-| k = 3 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 11 || 11 |-| k = 4 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 13 || 13 |-| k = 5 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 13 || 13 |} Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.

В первой строке как только вместимость рюкзака <tex>w_{1} = 6, p_{1} = 5 n \geqslant 3</tex>, добавляем в рюкзак 1 предмет.

Рассмотрим <tex>w_{2} k = 43</tex>, p_{2} при каждом <tex>s \geqslant 5 (</tex>так как <tex>w_3 = 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>w_{3} = 3A(5, p_{3} = 1 13)</tex>.

<tex>w_{4} = 2'''Восстановление набора предметов, p_{4} = 3 </tex>из которых состоит максимально дорогой рюкзак.'''

Начиная с <tex>w_{5} = A(5, p_{5} 13)</tex> восстанавливаем ответ. Будем идти в обратном порядке по <tex>k</tex>. ''<font color= 6 "000000">Красным фоном обозначим наш путь</texfont>''

{| 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|| 14|| 15

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

| s k = 1 || 0|| 0|style="background:#FF0000"| 0|| 01 || 01 || 01 || 51 || 51 || 51 || 51 || 51 || 51 || 51 || 5|| 5|| 51

| s k = 2 || 0|| 0|| 0|1 | 0|6 | 3|| 3|| 5|style="background:#FF0000"| 56 || 56 || 57 || 87 || 87 || 87 || 87 || 87 || 87

| s k = 3|| 0 || 0|| 0|| 1|| 36 || 3style="background:#FF0000"|6 | 5|| 5|6 | 5|| 67 || 87 || 810 || 810 || 910 || 911 || 911

| s k = 4 || 0|| 0|| 31 || 3|| 3|| 46 || 6|| 6|| 87 || 87 || 810 || 910 || 1110 || 1113 || 11|style="background:#FF0000"| 1213

| s k = 5 || 0|| 0|| 31 || 3|| 36 || 6|| 6|| 97 || 97 || 910 || 10 || 1210 || 1213 || 14|| 14|style="background:#FF0000"| 14 13

Рассмотрим стоку Таким образом, в набор входит <tex>s = 12</tex>и <tex>4</tex> предмет. То есть можно использовать только первый предмет, у которого

Стоимость рюкзака: <tex>w_1 = 6, p_1 + 7 = 513</tex>.

Вес рюкзака: <tex>A(1,n) 4 + 8 = 012</tex> при <tex>n \le 5</tex>,

<tex>A=Другие задачи семейства===Ограниченный рюкзак=={{Задача|definition ='''Ограниченный рюкзак''' (1,nангл. ''Bounded Knapsack Problem'') = 5</tex> при <tex> n \ge 6 </tex>— обобщение классической задачи, так как <tex>w_1 \le n</tex>когда любой предмет может быть взят некоторое количество раз.}}

===Формулировка Задачи===Каждый предмет может быть выбран ограниченное <tex>w_1 = 6, p_1 = 5b_i</tex> число раз.Задача выбрать число <tex>x_i</tex> предметов каждого типа так, чтобы

* максимизировать общую стоимость: <tex>w_2 \sum_{i= 4, p_2 = 31}^N p_ix_i</tex> ;

* выполнялось условие совместности: <tex>A(2, n) \sum_{i= A(1,n)</tex>, при <tex>n }^N w_ix_i \le 3</tex>, так как нельзя положить в рюкзак <tex>2leqslant W</tex> предмет. ;

где <tex>Ax_i \in (20,n) = max(A(1,n)\dots, A(1,n-w_{2}) + p_{2}b_i)</tex>, при остальных для всех <tex>ni= 1,2,\dots,N</tex>. А именно:

===Варианты решения===При небольших <tex>A(2,4) = max(0, 0 + 3) = 3b_i</tex>решается сведением к классической задаче о рюкзаке. В иных случаях:* Методом ветвей и границ.* Методом динамического программирования.

===Метод динамического программирования===Пусть <tex>Ad(2i,5c) = max(0</tex> максимальная стоимость любого возможного числа предметов типов от 1 до <tex>i</tex>, 0 + 3) = 3суммарным весом до <tex>c</tex>.

Заполним <tex>Ad(20,6) = max(5, 0 + 3c) = 5</tex>нулями.

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

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

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>Ad(2,9) = max(5, 0 + 3c) = 5</tex>вместо двумерного.

После выполнения в <tex>Ad(2N,10W) = max(5, 5 + 3) = 8</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, все вместимости <tex/font>A'' d[i][c] = d[i - 1][c] '''for''' l = min(2b[i],11c / w[i]) '''downto''' 1 ''<font color="green">//Ищем l для которого выполняется максимум </font>'' d[i][c] = max(5d[i][c], 5 d[i - 1][c - l * w[i]] + 3p[i] * l) = 8</tex>

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

Максимальная стоимость рюкзака находится в ===Формулировка Задачи===Каждый предмет может быть выбран любое число раз.Задача выбрать количество <tex>A(5, 15)x_i</tex>.предметов каждого типа так, чтобы

Сравниваем *выполнялось условие совместности: <tex>A(5, 15) \sum_{i= 14</tex> и <tex>A(4, 15) = 12</tex>. Не равны. Следовательно, <tex>5</tex> предмет входит в искомый набор, переходим к <tex>4</tex> предмету с весом рюкзака <tex>1}^N w_ix_i \leqslant W - w_5</tex>. То есть <tex>15 - 5 = 10</tex>;

Сравниваем где <tex>A(4, 10) = 8x_i \geqslant 0 </tex> и целое, для всех <tex>A(3i= 1, 10) = 8</tex>. Равны. Следовательно2, <tex>4</tex> предмет не входит в набор\dots, переходим к <tex>3N</tex> предмету с тем же весом рюкзака.

Сравниваем <tex>A(3, 10) = 8</tex> ==Варианты решения===Самые распространенные методы точного решения это:* Метод ветвей и <tex>A(2, 10) = 8</tex>. Равныграниц. Следовательно, <tex>4</tex> предмет не входит в набор, переходим к <tex>2</tex> предмету с тем же весом рюкзака* Метод динамического программирования.

Сравниваем ===Метод динамического программирования===Пусть <tex>Ad(2i, 10c) = 2</tex> и <tex>A(- максимальная стоимость любого количества вещей типов от 1, 10) = 5</tex>. Не равны. Следовательно, <tex>2до </tex> предмет входит в набор, уменьшаем вес рюкзака на <tex>w_2i</tex>, переходим к суммарным весом до <tex>1c</tex> предметувключительно.

Сравниваем Заполним <tex>A(1, 6) = 5</tex> и <tex>Ad(0, 6c) = 0</tex>. Не равны. Следовательно, <tex>1</tex> предмет входит в наборнулями.

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

Стоимость рюкзака <tex>d(i,c) = 5 + 3 \begin{cases} d(i - 1, c) & for\ c = 0, \dots, w_i - 1; \\ \max(d(i - 1, c), d(i, c - w_i) + 6 p_i) & for\ c = 14w_i, \dots, W; \end{cases}</tex>

Вес рюкзака После выполнения в <tex>= 6 + 4 + 5 = 15d(N,W) </tex>будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу: <tex> d(c) =\max(d(c), d(c - w_i) + p_i) </tex>; Сложность алгоритма <tex>O(NW)</tex>. = Литература =Непрерывный рюкзак=={{Задача|definition ='''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любую дробную часть от предмета, при этом удельная стоимость сохраняется.}} ===Формулировка Задачи===Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы *максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_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''' ==Задача о суммах подмножеств=={{Задача|definition ='''Задача о суммах подмножеств''' (англ. ''Subset sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.}} ===Формулировка Задачи===Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы *максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_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>. ===Варианты решения===Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:* Метод динамического программирования.* Использовать различные сложные алгоритмы <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><ref>Koiliaris, Konstantinos; Xu, Chao (2015-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</ref>. ===Метод динамического программирования===Пусть <tex>d(i,c)</tex> максимальная сумма <tex>\leqslant c</tex>, подмножества взятого из <tex> 1, \dots,\ i</tex> элементов. Заполним <tex>d(0,c)</tex> нулями. Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле: <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> После выполнения в <tex> d(N,W) </tex> будет лежать максимальная сумма подмножества, не превышающая заданное значение. Сложность алгоритма <tex>O(NW)</tex>. ==Задача о размене=={{Задача|definition ='''Задача о размене''' (англ. ''Change-Making problem'') — имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</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 \geqslant 0 </tex> целое, для всех <tex> i= 1,2,\dots,N</tex>.===Варианты решения===Самые распространенные методы точного решения это:* Метод ветвей и границ.* Метод динамического программирования. ===Метод динамического программирования===Пусть <tex>d(i,c)</tex> минимальное число предметов, типов от 1 до <tex>i</tex>, необходимое, чтобы заполнить рюкзак вместимостью <tex>c</tex>. Пусть <tex>d(0,0) = 0</tex>, а <tex>d(0,c) = \inf</tex> для всех <tex>c > 0</tex>.  Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле: <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(N,W) </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>. ==Задача об упаковке=={{Задача|definition ='''Задача об упаковке''' (англ. ''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} \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>. <tex> y_i = 1 </tex> если <tex> i</tex> рюкзак используется. Иначе <tex> y_i = 0 </tex>. ===Варианты решения===Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ. ==Мультипликативный рюкзак=={{Задача|definition ='''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\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} \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>.  <tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>. ===Варианты решения===Применение динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ. ==Задача о назначении=={{Задача|definition ='''Задача о назначении''' (англ. ''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> соответственно. }} Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.===Формулировка Задачи=== Максимизировать стоимость выбранных предметов <tex>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}</tex>, при выполнении условия совместности <tex>\sum_{j=1}^N w_{ij} x_{ij} \leqslant W_i \qquad i=1, \ldots, M</tex>. <tex> \sum_{i=1}^M x_{ij} \leqslant 1 \qquad j=1, \ldots, N</tex>. <tex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</tex>. ===Варианты решения===Применение динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ. == См. также ==* [[Класс NP]]* [[Метод четырех русских для умножения матриц]]* [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]* [[Meet-in-the-middle]] == Источники информации ==