Задача о рюкзаке — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 129 промежуточных версий 19 участников)
Строка 1: Строка 1:
'''Задача о рюкзаке''' — дано <tex>k</tex> предметов, i-й предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.
+
{{Задача
 +
|definition =
 +
'''Задача о рюкзаке '''(''англ. Knapsack problem'') — дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.
 +
}}
  
 
== Формулировка задачи ==
 
== Формулировка задачи ==
  
Дано <tex>k</tex> предметов, <tex>W</tex> - вместимость рюкзака, <tex>w=\{w_{1},w_{2},...,w_{k}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{k}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно определить набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{k}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет включен в набор, <tex> b_{i} = 0 </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> не включен, и такой что:
  
1. <tex>b_{1} w_{1}+ ... + b_{k} w_{k} \le W</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> максимальна.
  
2. <tex>b_{1} p_{1}+ ... + b_{k} k_{k} </tex> максимальна.
+
== Варианты решения ==
 +
 
 +
Задачу о рюкзаке можно решить несколькими способами:
 +
 
 +
* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.
  
== Варианты решения ==
+
* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}{N}) </tex>
  
'''Задачу о рюкзаке можно решить несколькими способами:'''
+
* Метод динамического программирования. Сложность — <tex>O(NW)</tex>.
  
1. Перебирая все подмножества набора из k предметов. Сложность такого решения <tex>O({2^{k}})</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}) </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>.
  
3. Метод динамического программирование. Сложность - <tex>O(k \times W)</tex>. Рассмотрим этот алгоритм подробнее.
+
<tex>A(k, 0) = 0</tex>
  
== Алгоритм <tex>O(k \times W)</tex> ==
+
<tex>A(0, s) = 0</tex>
  
Пусть <tex>A(s, n)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости n, если можно использовать только первые s предметов из заданных k.
+
Найдем <tex>A(k, s)</tex>. Возможны 2 варианта:
  
<tex>A(s, 0) = 0</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(0, n) = 0</tex>
+
<tex>
 +
A(k, s) =
 +
\begin{cases}
 +
A(k-1, s), & b_k = 0 \\
 +
A(k-1, s-w_k) + p_k, & b_k = 1 \\
 +
\end{cases}
 +
</tex>
  
Найдем <tex>A(s, n)</tex>. Возможны 2 варианта:
+
То есть:
 +
<tex>A(k,s) = \max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})</tex>
  
1. Если предмет <tex>s</tex> не попал в рюкзак. Тогда <tex>A(s, n) = A(s-1, n)</tex>
+
Стоимость искомого набора равна <tex>A(N,W)</tex>, так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака <tex>W</tex>.
  
2. Если <tex>s</tex> попал в рюкзак. Тогда <tex>A(s, n) = A(s-1, n-w_{s}) + p_{s}</tex>
+
'''Восстановим набор предметов, входящих в рюкзак'''
  
Таким образом:
+
Будем определять, входит ли <tex>n_i</tex> предмет в искомый набор. Начинаем с элемента <tex>A(i,w)</tex>, где <tex>i = N</tex>, <tex>w = W</tex>. Для этого сравниваем <tex>A(i,w)</tex> со следующими значениями:
<tex>A(s,n) = max(A(s-1,n), A(s-1,n-w_{s}) + p_{s})</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>k</tex> - последний предмет в рюкзак. Если <tex>A(k, W)</tex> равно <tex>A(k-1, W)</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>O(kW)</tex>
+
Метод динамического программирование всё равно не позволяет решать задачу за полиномиальное время, потому что его сложность зависит от максимального веса. Задача о ранце (или задача о рюкзаке) — одна из [[Класс NP|NP-полных]] задач комбинаторной оптимизации.
  
 
== Реализация ==
 
== Реализация ==
Сначала генерируем <tex>А</tex>
+
Сначала генерируем <tex>A</tex>.
  
  for i = 0 ... W
+
  '''for''' i = 0 '''to''' w
 
   A[0][i] = 0
 
   A[0][i] = 0
  for i = 0 ... k
+
  '''for''' i = 0 '''to''' n
   A[i][0] = 0                         {Первые элементы приравниваем 0}
+
   A[i][0] = 0                                               ''<font color="green">//Первые элементы приравниваем к 0</font>''
  for s = 1 ... k                
+
  '''for''' k = 1 '''to''' n                
   for n = 0 ... W                    {Перебираем для каждого s, все n}
+
   '''for''' s = 1 '''to''' w                                            ''<font color="green">//Перебираем для каждого k все вместимости</font>''
     if n >= w[s]                     {Если текущий предмет можно положить в рюкзак}
+
     '''if''' s >= w[k]                                           ''<font color="green">//Если текущий предмет вмещается в рюкзак</font>''
       A[s][n] = max(A[s-1][n], A[s-1][n-w[s]]+p[s]) {выбираем класть его или нет}
+
       A[k][s] = max(A[k - 1][s], A[k - 1][s - w[k]] + p[k]) ''<font color="green">//Выбираем класть его или нет</font>''
     else  
+
     '''else'''
       A[s][n] = A[s-1][n]             {иначе, не кладем}
+
       A[k][s] = A[k - 1][s]                                 ''<font color="green">//Иначе, не кладем</font>''
  
 
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
 
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
  
  void findAns(s, n)
+
  '''function''' findAns('''int''' k, '''int''' s)
   if A[s][n] == 0  
+
   '''if''' A[k][s] == 0  
     return
+
     '''return'''
   if A[s-1][n] == A[s][n]
+
   '''if''' A[k - 1][s] == A[k][s]
     findAns(s-1, n)
+
     findAns(k - 1, s)
   else  
+
   '''else'''
     findAns(s-1, n - w[s]);
+
     findAns(k - 1, s - w[k])
     ans.push(s);
+
     ans.push(k)
 +
 
 +
Сложность алгоритма <tex>O(NW)</tex>
  
 
== Пример ==
 
== Пример ==
  
<tex>W = 13, k = 5</tex>  
+
<tex>W = 13, N = 5</tex>  
  
 
<tex>w_{1} = 3, p_{1} = 1 </tex>
 
<tex>w_{1} = 3, p_{1} = 1 </tex>
Строка 81: Строка 99:
 
<tex>w_{5} = 9, p_{5} = 6 </tex>
 
<tex>w_{5} = 9, p_{5} = 6 </tex>
  
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
+
{|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>n \geqslant 3</tex>, добавляем в рюкзак 1 предмет.
 +
 
 +
Рассмотрим <tex>k = 3</tex>, при каждом <tex>s \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>A(5, 13)</tex> восстанавливаем ответ. Будем идти в обратном порядке по <tex>k</tex>. ''<font color="000000">Красным фоном обозначим наш путь</font>''
 +
 
 +
{|border="1" class="wikitable" style="text-align:center" width="75%"
 +
|-
 +
!        || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9  || 10  || 11  || 12  || 13
 
|-
 
|-
| s = 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0
+
| k = 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0   || 0   || 0   || 0
 
|-
 
|-
| s = 1|| 0|| 0|| 0|| 1|| 1|| 1|| 1|| 1|| 1|| 1|| 1|| 1|| 1|| 1
+
| k = 1 || 0 ||style="background:#FF0000"| 0 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1   || 1   || 1   || 1
 
|-
 
|-
| s = 2|| 0|| 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 7|| 7|| 7|| 7|| 7
+
| k = 2 || 0 || 0 || 1 || 6 ||style="background:#FF0000"| 6 || 6 || 7 || 7 || 7 || 7   || 7   || 7   || 7
 
|-
 
|-
| s = 3|| 0|| 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 10|| 10|| 10|| 11|| 11
+
| k = 3 || 0 || 0 || 1 || 6 ||style="background:#FF0000"| 6 || 6 || 7 || 7 || 10 || 10 || 10 || 11 || 11
 
|-
 
|-
| s = 4|| 0|| 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 10|| 10|| 10|| 13|| 13
+
| k = 4 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 13 ||style="background:#FF0000"| 13
 
|-
 
|-
| s = 5|| 0|| 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 ||style="background:#FF0000"| 13
 
|}
 
|}
Числа от 0 до 15 в первой строчке обозначают вместимость рюкзака.
 
  
В первой строке как только вместимость рюкзака <tex>n /ge 3</tex>, добавляем в рюкзак 1 предмет.
+
Таким образом, в набор входит <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> предметов каждого типа так, чтобы
 +
 
 +
* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_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>.
 +
 
 +
===Варианты решения===
 +
При небольших <tex>b_i</tex> решается сведением к классической задаче о рюкзаке. В иных случаях:
 +
* Методом ветвей и границ.
 +
* Методом динамического программирования.
 +
 
 +
===Метод динамического программирования===
 +
Пусть <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> от 1 до <tex>W</tex>, по рекуррентной формуле:
 +
 
 +
<tex>d(i,c) = \max(d(i, c), 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> вместо двумерного.
 +
 
 +
После выполнения в <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> предметов каждого типа так, чтобы
 +
 
 +
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
 +
 
 +
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant 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,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(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>2</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>A(5, 15)</tex>.
+
Часто задачу ставят как, дать сдачу наименьшим количеством монет.
 +
===Формулировка Задачи===
 +
Каждый предмет может быть выбран любое число раз.
 +
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы
  
'''Теперь восстановим набор предметов, из которых состоит максимально дорогой рюкзак.'''
+
*минимизировать количество взятых предметов: <tex>\sum_{i=1}^N x_i</tex>;
  
Сравниваем <tex>A(5, 15) = 14</tex> и <tex>A(4, 15) = 12</tex>. Не равны. Следовательно, <tex>5</tex> предмет входит в искомый набор, переходим к <tex>4</tex> предмету с весом рюкзака <tex>W - w_5</tex>. То есть <tex>15 - 5 = 10</tex>
+
*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;
  
Сравниваем <tex>A(4, 10) = 8</tex> и <tex>A(3, 10) = 8</tex>. Равны. Следовательно, <tex>4</tex> предмет не входит в набор, переходим к <tex>3</tex> предмету с тем же весом рюкзака.
+
Где <tex> x_i \geqslant 0 </tex> целое,  для всех <tex> i= 1,2,\dots,N</tex>.
 +
===Варианты решения===
 +
Самые распространенные методы точного решения это:
 +
* Метод ветвей и границ.
 +
* Метод динамического программирования.
  
Сравниваем <tex>A(3, 10) = 8</tex> и <tex>A(2, 10) = 8</tex>. Равны. Следовательно, <tex>4</tex> предмет не входит в набор, переходим к <tex>2</tex> предмету с тем же весом рюкзака.
+
===Метод динамического программирования===
 +
Пусть <tex>d(i,c)</tex> минимальное число предметов, типов от 1 до <tex>i</tex>, необходимое, чтобы заполнить рюкзак вместимостью <tex>c</tex>.
  
Сравниваем <tex>A(2, 10) = 2</tex> и <tex>A(1, 10) = 5</tex>. Не равны. Следовательно, <tex>2</tex> предмет входит в набор, уменьшаем вес рюкзака на <tex>w_2</tex>, переходим к <tex>1</tex> предмету.
+
Пусть <tex>d(0,0) = 0</tex>, а <tex>d(0,c) = \inf</tex> для всех <tex>c > 0</tex>.  
  
Сравниваем <tex>A(1, 6) = 5</tex> и <tex>A(0, 6) = 0</tex>. Не равны. Следовательно, <tex>1</tex> предмет входит в набор.
+
Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:
  
Таким образом, набор состоит из <tex>1, 2, 5</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>= 5 + 3 + 6 = 14</tex>
+
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.
  
Вес рюкзака <tex>= 6 + 4 + 5 = 15</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]]
 +
 
 +
== Источники информации ==
 
*[http://informatics.mccme.ru/moodle/mod/book/view.php?id=815&chapterid=60 Дистанционная подготовка по информатике]
 
*[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 г. — ISBN 0-471-92420-2
 +
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Динамическое программирование]]
 
[[Категория: Динамическое программирование]]

Текущая версия на 19:19, 4 сентября 2022

Задача:
Задача о рюкзаке (англ. Knapsack problem) — дано [math]N[/math] предметов, [math]n_i[/math] предмет имеет массу [math] w_i \gt 0[/math] и стоимость [math] p_i \gt 0[/math]. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины [math]W[/math] (вместимость рюкзака), а суммарная стоимость была максимальна.


Содержание

Формулировка задачи

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

  1. [math]b_{1} w_{1}+ \dots + b_{N} w_{N} \leqslant W[/math]
  2. [math]b_{1} p_{1}+ \dots + b_{N} p_{N} [/math] максимальна.

Варианты решения

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

  • Перебирать все подмножества набора из N предметов. Сложность такого решения [math]O({2^{N}})[/math].
  • Методом Meet-in-the-middle. Сложность решения [math] O({2^{N/2}}{N}) [/math]
  • Метод динамического программирования. Сложность — [math]O(NW)[/math].

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

Пусть [math]A(k, s)[/math] есть максимальная стоимость предметов, которые можно уложить в рюкзак вместимости [math]s[/math], если можно использовать только первые [math]k[/math] предметов, то есть [math]\{n_1,n_2,\dots,n_k\}[/math], назовем этот набор допустимых предметов для [math]A(k,s)[/math].

[math]A(k, 0) = 0[/math]

[math]A(0, s) = 0[/math]

Найдем [math]A(k, s)[/math]. Возможны 2 варианта:

  1. Если предмет [math]k[/math] не попал в рюкзак. Тогда [math]A(k, s)[/math] равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов [math]\{n_1,n_2,\dots,n_{k-1}\}[/math], то есть [math]A(k,s) = A(k-1, s)[/math]
  2. Если [math]k[/math] попал в рюкзак. Тогда [math]A(k, s)[/math] равно максимальной стоимости рюкзака, где вес [math]s[/math] уменьшаем на вес [math]k[/math]-ого предмета и набор допустимых предметов [math]\{n_1,n_2,\dots,n_{k-1}\}[/math] плюс стоимость [math]k[/math], то есть [math]A(k-1, s-w_k) + p_k[/math]

[math] A(k, s) = \begin{cases} A(k-1, s), & b_k = 0 \\ A(k-1, s-w_k) + p_k, & b_k = 1 \\ \end{cases} [/math]

То есть: [math]A(k,s) = \max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})[/math]

Стоимость искомого набора равна [math]A(N,W)[/math], так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака [math]W[/math].

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

Будем определять, входит ли [math]n_i[/math] предмет в искомый набор. Начинаем с элемента [math]A(i,w)[/math], где [math]i = N[/math], [math]w = W[/math]. Для этого сравниваем [math]A(i,w)[/math] со следующими значениями:

  1. Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов [math]\{n_1,n_2,\dots,n_{i-1}\}[/math], то есть [math]A(i-1, w)[/math]
  2. Максимальная стоимость рюкзака с вместимостью на [math]w_i[/math] меньше и набором допустимых предметов [math]\{n_1,n_2,\dots,n_{i-1}\}[/math] плюс стоимость [math]p_i[/math], то есть [math]A(i-1, w-w_i)+p_i[/math]

Заметим, что при построении [math]A[/math] мы выбирали максимум из этих значений и записывали в [math]A(i, w)[/math]. Тогда будем сравнивать [math]A(i, w)[/math] c [math]A(i-1, w)[/math], если равны, тогда [math]n_i[/math] не входит в искомый набор, иначе входит.

Метод динамического программирование всё равно не позволяет решать задачу за полиномиальное время, потому что его сложность зависит от максимального веса. Задача о ранце (или задача о рюкзаке) — одна из NP-полных задач комбинаторной оптимизации.

Реализация

Сначала генерируем [math]A[/math].

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

Затем найдем набор [math]ans[/math] предметов, входящих в рюкзак, рекурсивной функцией:

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)

Сложность алгоритма [math]O(NW)[/math]

Пример

[math]W = 13, N = 5[/math]

[math]w_{1} = 3, p_{1} = 1 [/math]

[math]w_{2} = 4, p_{2} = 6 [/math]

[math]w_{3} = 5, p_{3} = 4 [/math]

[math]w_{4} = 8, p_{4} = 7 [/math]

[math]w_{5} = 9, p_{5} = 6 [/math]

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 в первой строчке обозначают вместимость рюкзака.

В первой строке как только вместимость рюкзака [math]n \geqslant 3[/math], добавляем в рюкзак 1 предмет.

Рассмотрим [math]k = 3[/math], при каждом [math]s \geqslant 5 ([/math]так как [math]w_3 = 5)[/math] сравниваем [math]A[k-1][s][/math] и [math]A[k-1][s-w_3]+p_3[/math] и записываем в [math]A[k][s][/math] стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимости третьего предмета плюс стоимость рюкзака с вместимостью на [math]w_3[/math] меньше.

Максимальная стоимость рюкзака находится в [math]A(5, 13)[/math].

Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.

Начиная с [math]A(5, 13)[/math] восстанавливаем ответ. Будем идти в обратном порядке по [math]k[/math]. Красным фоном обозначим наш путь

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

Таким образом, в набор входит [math]2[/math] и [math]4[/math] предмет.

Стоимость рюкзака: [math] 6 + 7 = 13[/math]

Вес рюкзака: [math] 4 + 8 = 12[/math]

Другие задачи семейства

Ограниченный рюкзак

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


Формулировка Задачи

Каждый предмет может быть выбран ограниченное [math]b_i[/math] число раз. Задача выбрать число [math]x_i[/math] предметов каждого типа так, чтобы

  • максимизировать общую стоимость: [math]\sum_{i=1}^N p_ix_i[/math];
  • выполнялось условие совместности: [math]\sum_{i=1}^N w_ix_i \leqslant W[/math];

где [math] x_i \in (0,1,\dots,b_i)[/math] для всех [math] i= 1,2,\dots,N[/math].

Варианты решения

При небольших [math]b_i[/math] решается сведением к классической задаче о рюкзаке. В иных случаях:

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

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

Пусть [math]d(i,c)[/math] максимальная стоимость любого возможного числа предметов типов от 1 до [math]i[/math], суммарным весом до [math]c[/math].

Заполним [math]d(0,c)[/math] нулями.

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

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

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

После выполнения в [math] d(N,W) [/math] будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Реализация

for i = 0 to w                               //База
  d[0][i] = 0
for i = 1 to n             
  for c = 1 to w                             //Перебираем для каждого i, все вместимости 
    d[i][c] = d[i - 1][c]
    for l = min(b[i], c / w[i]) downto 1     //Ищем l для которого выполняется максимум 
        d[i][c] =  max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l)

Сложность алгоритма [math]O(NW^2)[/math].

Неограниченный рюкзак

Задача:
Неограниченный рюкзак (англ.Unbounded Knapsack Problem) — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.


Формулировка Задачи

Каждый предмет может быть выбран любое число раз. Задача выбрать количество [math]x_i[/math] предметов каждого типа так, чтобы

  • максимизировать общую стоимость: [math]\sum_{i=1}^N p_ix_i[/math];
  • выполнялось условие совместности: [math]\sum_{i=1}^N w_ix_i \leqslant W[/math];

где [math] x_i \geqslant 0 [/math] целое, для всех [math] i= 1,2,\dots,N[/math].

Варианты решения

Самые распространенные методы точного решения это:

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

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

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

Заполним [math]d(0,c)[/math] нулями.

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

[math] 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} [/math]

После выполнения в [math] d(N,W) [/math] будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

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

[math] d(c) = \max(d(c), d(c - w_i) + p_i) [/math];

Сложность алгоритма [math]O(NW)[/math].

Непрерывный рюкзак

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


Формулировка Задачи

Задача выбрать часть [math]x_i[/math] каждого предмета так, чтобы

  • максимизировать общую стоимость: [math]\sum_{i=1}^N p_ix_i[/math];
  • выполнялось условие совместности: [math]\sum_{i=1}^N w_ix_i \leqslant W[/math];

где [math] 0 \leqslant x_i \leqslant 1[/math] дробное, для всех [math] i= 1,2,\dots,N[/math].

Варианты решения

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

Реализация

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

Задача о суммах подмножеств

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


Формулировка Задачи

Нужно выбрать подмножество так, чтобы сумма ближе всего к [math]W[/math], но не превысила его. Формально, нужно найти набор бинарных величин [math]x_i[/math], так чтобы

  • максимизировать общую стоимость: [math]\sum_{i=1}^N w_ix_i[/math];
  • выполнялось условие совместности: [math]\sum_{i=1}^N w_ix_i \leqslant W[/math];

[math] x_j = 1 [/math] если [math] j[/math] предмет назначен рюкзаку, иначе [math] x_{ij} = 0 [/math], для всех [math] i= 1,2,\dots,N[/math].

Варианты решения

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

  • Метод динамического программирования.
  • Использовать различные сложные алгоритмы [1][2][3][4].

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

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

Заполним [math]d(0,c)[/math] нулями.

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

[math] 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} [/math]

После выполнения в [math] d(N,W) [/math] будет лежать максимальная сумма подмножества, не превышающая заданное значение.

Сложность алгоритма [math]O(NW)[/math].

Задача о размене

Задача:
Задача о размене (англ. Change-Making problem) — имеются [math] N [/math] неисчерпаемых типов предметов с весами [math]w_i[/math]. Нужно наполнить рюкзак предметами с суммарным весом [math]W[/math].


Часто задачу ставят как, дать сдачу наименьшим количеством монет.

Формулировка Задачи

Каждый предмет может быть выбран любое число раз. Задача выбрать количество [math]x_i[/math] предметов каждого типа так, чтобы

  • минимизировать количество взятых предметов: [math]\sum_{i=1}^N x_i[/math];
  • сумма весов выбранных предметов равнялась вместимости рюкзака: [math]\sum_{i=1}^N w_ix_i = W[/math];

Где [math] x_i \geqslant 0 [/math] целое, для всех [math] i= 1,2,\dots,N[/math].

Варианты решения

Самые распространенные методы точного решения это:

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

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

Пусть [math]d(i,c)[/math] минимальное число предметов, типов от 1 до [math]i[/math], необходимое, чтобы заполнить рюкзак вместимостью [math]c[/math].

Пусть [math]d(0,0) = 0[/math], а [math]d(0,c) = \inf[/math] для всех [math]c \gt 0[/math].

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

[math] 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} [/math]

После выполнения в [math] d(N,W) [/math] будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

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

[math] d(c) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, \dots, W[/math].

Сложность алгоритма [math]O(NW)[/math].

Задача об упаковке

Задача:
Задача об упаковке (англ. Bin Packing Problem) — имеются [math] N [/math] рюкзаков вместимости [math] W [/math] и столько же предметов с весами [math]w_i[/math]. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.


Формулировка Задачи

Математически задачу можно представить так:

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

[math] x_{ij} = 1 [/math] если [math] j[/math] предмет назначен [math]i [/math] рюкзаку. Иначе [math] x_{ij} = 0 [/math].

[math] y_i = 1 [/math] если [math] i[/math] рюкзак используется. Иначе [math] y_i = 0 [/math].

Варианты решения

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

Мультипликативный рюкзак

Задача:
Мультипликативный рюкзак (англ. Multiple Knapsack Problem) — есть [math]N[/math] предметов и [math]M[/math] рюкзаков ([math]M\leqslant N[/math]). У каждого рюкзака своя вместимость [math]W_i[/math]. Задача: выбрать [math]M[/math] не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.


Формулировка Задачи

Максимизировать [math]\sum_{i=1}^M \sum_{j=1}^{N} p_jx_{ij}[/math]

так, чтобы [math]\sum_{i=1}^N w_jx_{ij} \leqslant W_i[/math] выполнялось для всех [math] i= 1,2,\dots,N[/math].

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


[math] x_{ij} = 1 [/math] если [math] j[/math] предмет назначен [math]i [/math] рюкзаку. Иначе [math] x_{ij} = 0 [/math].

Варианты решения

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

Задача о назначении

Задача:
Задача о назначении (англ. Generalized Assignment Problem) — Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть [math]N[/math] предметов и [math]M[/math] рюкзаков ([math]M\leqslant N[/math]). У каждого рюкзака своя вместимость [math]W_i[/math], у [math] j [/math] предмета [math] p_{ij} [/math] стоимость и вес, при помещении его в [math] i [/math] рюкзак, равны [math] p_{ij} [/math] и [math] w_{ij} [/math] соответственно.


Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.

Формулировка Задачи

Максимизировать стоимость выбранных предметов [math]\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}[/math],

при выполнении условия совместности [math]\sum_{j=1}^N w_{ij} x_{ij} \leqslant W_i \qquad i=1, \ldots, M[/math].

[math] \sum_{i=1}^M x_{ij} \leqslant 1 \qquad j=1, \ldots, N[/math].

[math] x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N[/math].

Варианты решения

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

См. также

Источники информации

  • http://hjemmesider.diku.dk/~pisinger/codes.html
  • Pisinger D (1999). "Linear Time Algorithms for Knapsack Problems with Bounded Weights". Journal of Algorithms, Volume 33, Number 1, October 1999, pp. 1–14
  • Koiliaris, Konstantinos; Xu, Chao (2015-07-08). "A Faster Pseudopolynomial Time Algorithm for Subset Sum".
  • 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
  • Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_рюкзаке&oldid=84882»