1632
правки
Изменения
м
'''Задачу о рюкзаке можно решить несколькими способами:'''
Если короче: #<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> Выберем из этих двух значений максимальное:
| || 0! || 1|| 2|| 3|| 4|| 5|| 6|| 7|| 8|| 9 || 10 || 11 || 12 || 13
[[Файл: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> меньше.
[[Файл{|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 |}
и где <mathtex> x_i \in (0,1,...\dots,b_i)</mathtex> для всех <mathtex> i= 1,2,...\dots,N</mathtex>.
==Не ограниченный рюкзак==
'''Не ограниченный рюкзак'''' (англ. "Unbounded Knapsack Problem") - обобщение ограниченого рюкзака, в котором любой предмет может быть выбран любое количество раз.
Если не нужно востанавливать ответ, то можно использовать одномерный массив После выполнения в <tex>d(cN,W)</tex> вместо двумерногобудет лежать максимальная стоимость предметов, и использовать формулу:помещающихся в рюкзак.
После выполнения в <tex> d(Nc) = \max(d(c),Wd(c - w_i) + p_i) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.;
==Непрерывный рюкзак==
""Непрерывный рюкзак"" (англ. "Continuous knapsack problem") - вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
Изменение формулировки значительно облегчает Возможность брать любую часть от предмета сильно упрощает задачу. Жадный алгоритм дает оптимальное решение в данном случае. === Реализация === sort() ''<font color="green">//Сортируем в порядке убывания удельной стоимости.</font>''
максимизировать общую стоимость*минимизировать количество взятых предметов: <mathtex>\sum_{i=1}^N p_ix_ix_i</mathtex>;
выполнялось условие на совместность*сумма весов выбранных предметов равнялась вместимости рюкзака: <mathtex>\sum_{i=1}^N w_ix_i \le = W</math> <math> x_i \in {0,1} </math>, для всех <math> i= 1,2,...,N</mathtex>;
Заполним Пусть <tex>d(0,0) = 0</tex>, а <tex>d(0,c)= \inf</tex> для всех <tex>c > 0</tex> нулями.
Если не нужно востанавливать ответ, то можно использовать одномерный массив После выполнения в <tex>d(cN,W)</tex> вместо двумерногобудет лежать максимальная стоимость предметов, и использовать формулу:помещающихся в рюкзак.
После выполнения в <tex> d(Nc) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, \dots,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.
rollbackEdits.php mass rollback
{{Задача|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> максимальна.
== Варианты решения ==
* Перебирать все подмножества набора из 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 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>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>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> не входит в искомый набор, иначе входит.
Метод динамического программирование всё равно не позволяет решать задачу за полиномиальное время, потому что его сложность зависит от максимального веса. Задача о ранце (или задача о рюкзаке) — одна из [[Класс NP|NP-полных]] задач комбинаторной оптимизации.
== Реализация ==
Сначала генерируем <tex>A</tex>.
'''for ''' i = 0..W'''to''' w
A[0][i] = 0
'''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>''
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
'''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>
== Пример ==
<tex>w_{5} = 9, p_{5} = 6 </tex>
{| classborder="wikitable1" cellpaddingclass="4wikitable" borderstyle="1text-align:center" stylewidth="border-collapse: collapse;75%"
|-
|-
| 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
|}
Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.
В первой строке как только вместимость рюкзака <tex>n \ge geqslant 3</tex>, добавляем в рюкзак 1 предмет.
Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>.
'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''
Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ.Будем идти в обратном порядке по <tex>k</tex>. ''<font color="000000">Красным фоном обозначим наш путь</font>''
Таким образом, в набор входит <tex>2</tex> и <tex>4</tex> предмет.
Стоимость рюкзака : <tex>= 6 + 7 = 13</tex>
Вес рюкзака : <tex>= 4 + 8 = 12</tex>
=Другие задачи семейства=
==Ограниченый Ограниченный рюкзак =={{Задача|definition ='''Ограниченый Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') - — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.}}
===Формулировка Задачи===
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.
Задача выбрать число <tex>x_i</tex> предметов каждого типа так, чтобы
* максимизировать общую стоимость: <mathtex>\sum_{i=1}^N p_ix_i</mathtex>;
* выполнялось условие на совместностьсовместности: <mathtex>\sum_{i=1}^N w_ix_i \le leqslant W</mathtex>;
===Варианты решения===
При небольших <tex>b_i</tex> решается сведением к классической задаче о рюкзаке. В иных случаях:
* Методом ветвей и границ.* Методом динамического программирования.
===Метод динамического программирования===
Заполним <tex>d(0,c)</tex> нулями.
Тогда меняя 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> вместо двумерного.
После выполнения в <tex> d(N,W) </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]) '''downto''' 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(NW^2)</tex>.
==Неограниченный рюкзак==
{{Задача
|definition =
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
}}
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы
*максимизировать общую стоимость: <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> включительно .
Заполним <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, c - w_i) + p_i) & for\ c = w_i, ...\dots, W;
\end{cases}
</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> каждого предмета так, чтобы
*максимизировать общую стоимость: <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>.
===Варианты решения===
'''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>, так чтобы
*максимизировать общую стоимость: <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> элементов.
Заполним <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>
==Задача о размене==
{{Задача|definition ='''Задача о размене'''' (англ. ""''Change-Making problem'') - обобщение ограниченого рюкзака— имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>.}} Часто задачу ставят как, в котором любой предмет может быть выбран любое количество раздать сдачу наименьшим количеством монет.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</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> включительно .
Тогда меняя 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; \\ maxmin(d(i - 1, c), d(i, c - w_i) + p_i1) & for\ c = w_i, ...\dots, W;
\end{cases}
</tex>
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex> d(c) = max(d(c), d(c - w_i) + p_i) </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]] == Источники информации ==
*[http://informatics.mccme.ru/moodle/mod/book/view.php?id=815&chapterid=60 Дистанционная подготовка по информатике]
*[http://rosettacode.org/wiki/Knapsack_Problem Код для нескольких задач семейства на всевозможных языках]
*[http://www.diku.dk/users/pisinger/95-1.pdf David Pisinger Knapsack problems. — 1995]
*Silvano Martello, Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations— 1990 г. Silvano Martello, Paolo Toth.— ISBN 0-471-92420-2
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]