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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлена ссылка на NP-класс)
м (rollbackEdits.php mass rollback)
 
(не показаны 42 промежуточные версии 9 участников)
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
'''Задача о рюкзаке'''(''англ. Knapsack problem'') — дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.
+
'''Задача о рюкзаке '''(''англ. 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},...,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{N}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</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}+ ... + b_{N} w_{N} \le W</tex>
+
#<tex>b_{1} w_{1}+ \dots + b_{N} w_{N} \leqslant W</tex>
#<tex>b_{1} p_{1}+ ... + b_{N} p_{N} </tex> максимальна.
+
#<tex>b_{1} p_{1}+ \dots + b_{N} p_{N} </tex> максимальна.
  
 
== Варианты решения ==
 
== Варианты решения ==
Строка 17: Строка 17:
 
* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.
 
* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.
  
* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}\times{N}) </tex>
+
* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}{N}) </tex>
  
* Метод динамического программирования. Сложность — <tex>O(N \times W)</tex>.
+
* Метод динамического программирования. Сложность — <tex>O(NW)</tex>.
  
 
== Метод динамического программирования ==
 
== Метод динамического программирования ==
  
Пусть <tex>A(k, s)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,...,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</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, 0) = 0</tex>
Строка 31: Строка 31:
 
Найдем <tex>A(k, s)</tex>. Возможны 2 варианта:
 
Найдем <tex>A(k, s)</tex>. Возможны 2 варианта:
  
#Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex>, то есть <tex>A(k,s) = A(k-1, 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,...,n_{k-1}\}</tex> плюс стоимость <tex>k</tex>, то есть <tex>A(k-1, s-w_k) + p_k</tex>
+
# Если <tex>k</tex> попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака, где вес <tex>s</tex> уменьшаем на вес <tex>k</tex>-ого предмета и набор допустимых предметов <tex>\{n_1,n_2,\dots,n_{k-1}\}</tex> плюс стоимость <tex>k</tex>, то есть <tex>A(k-1, s-w_k) + p_k</tex>
  
 
<tex>
 
<tex>
Строка 43: Строка 43:
  
 
То есть:  
 
То есть:  
<tex>A(k,s) = max(A(k-1,s), 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>A(N,W)</tex>, так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака <tex>W</tex>.
Строка 51: Строка 51:
 
Будем определять, входит ли <tex>n_i</tex> предмет в искомый набор. Начинаем с элемента <tex>A(i,w)</tex>, где <tex>i = N</tex>, <tex>w = W</tex>. Для этого сравниваем <tex>A(i,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,...,n_{i-1}\}</tex>, то есть <tex>A(i-1, 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,...,n_{i-1}\}</tex> плюс стоимость <tex>p_i</tex>, то есть <tex>A(i-1, w-w_i)+p_i</tex>
+
#Максимальная стоимость рюкзака с вместимостью на <tex>w_i</tex> меньше и набором допустимых предметов <tex>\{n_1,n_2,\dots,n_{i-1}\}</tex> плюс стоимость <tex>p_i</tex>, то есть <tex>A(i-1, w-w_i)+p_i</tex>
  
 
Заметим, что при построении <tex>A</tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w)</tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит.
 
Заметим, что при построении <tex>A</tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w)</tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит.
  
Метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время, потому что задача о ранце (или задача о рюкзаке) — одна из [[Класс NP|NP-полных]] задач комбинаторной оптимизации.
+
Метод динамического программирование всё равно не позволяет решать задачу за полиномиальное время, потому что его сложность зависит от максимального веса. Задача о ранце (или задача о рюкзаке) — одна из [[Класс NP|NP-полных]] задач комбинаторной оптимизации.
  
 
== Реализация ==
 
== Реализация ==
 
Сначала генерируем <tex>A</tex>.  
 
Сначала генерируем <tex>A</tex>.  
  
  '''for''' i = 0..W
+
  '''for''' i = 0 '''to''' w
   A[0][i] = 0;
+
   A[0][i] = 0
  '''for''' i = 0..N
+
  '''for''' i = 0 '''to''' n
   A[i][0] = 0''<font color="green">// Первые элементы приравниваем к 0</font>''
+
   A[i][0] = 0                                               ''<font color="green">//Первые элементы приравниваем к 0</font>''
  '''for''' k = 1..N                
+
  '''for''' k = 1 '''to''' n                
   '''for''' s = 1..W  ''<font color="green">//Перебираем для каждого k все вместимости</font>''  
+
   '''for''' s = 1 '''to''' w                                            ''<font color="green">//Перебираем для каждого k все вместимости</font>''  
     '''if''' s >= w[k]   ''<font color="green">//Если текущий предмет вмещается в рюкзак</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>''  
+
       A[k][s] = max(A[k - 1][s], A[k - 1][s - w[k]] + p[k]) ''<font color="green">//Выбираем класть его или нет</font>''  
 
     '''else'''  
 
     '''else'''  
       A[k][s] = A[k-1][s];            ''<font color="green">//иначе, не кладем</font>''  
+
       A[k][s] = A[k - 1][s]                                 ''<font color="green">//Иначе, не кладем</font>''  
  
 
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
 
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
  
  findAns(k, s)
+
  '''function''' findAns('''int''' k, '''int''' s)
 
   '''if''' A[k][s] == 0  
 
   '''if''' A[k][s] == 0  
     '''return''';
+
     '''return'''
   '''if''' A[k-1][s] == A[k][s]
+
   '''if''' A[k - 1][s] == A[k][s]
     findAns(k-1, s);
+
     findAns(k - 1, s)
 
   '''else'''  
 
   '''else'''  
     findAns(k-1, s - w[k]);
+
     findAns(k - 1, s - w[k])
     ans.push(k);
+
     ans.push(k)
  
Сложность алгоритма <tex>O(N \times W)</tex>
+
Сложность алгоритма <tex>O(NW)</tex>
  
 
== Пример ==
 
== Пример ==
Строка 99: Строка 99:
 
<tex>w_{5} = 9, p_{5} = 6 </tex>
 
<tex>w_{5} = 9, p_{5} = 6 </tex>
  
[[Файл:Knapsack problem0.png]]
+
{|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 в первой строчке обозначают вместимость рюкзака.
 
Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.
  
В первой строке как только вместимость рюкзака <tex>n \ge 3</tex>, добавляем в рюкзак 1 предмет.
+
В первой строке как только вместимость рюкзака <tex>n \geqslant 3</tex>, добавляем в рюкзак 1 предмет.
  
Рассмотрим <tex>k = 3</tex>, при каждом <tex>s \ge 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>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>.
Строка 111: Строка 126:
 
'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''
 
'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''
  
Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ.
+
Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ. Будем идти в обратном порядке по <tex>k</tex>. ''<font color="000000">Красным фоном обозначим наш путь</font>''
  
[[Файл:Задача о рюкзаке3.png]]
+
{|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 ||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>2</tex> и <tex>4</tex> предмет.
 
Таким образом, в набор входит <tex>2</tex> и <tex>4</tex> предмет.
  
Стоимость рюкзака <tex>= 6 + 7 = 13</tex>
+
Стоимость рюкзака: <tex> 6 + 7 = 13</tex>
  
Вес рюкзака <tex>= 4 + 8 = 12</tex>
+
Вес рюкзака: <tex> 4 + 8 = 12</tex>
  
 
=Другие задачи семейства=
 
=Другие задачи семейства=
==Ограниченный рюкзак ==
+
==Ограниченный рюкзак==
 +
{{Задача
 +
|definition =
 
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.
 
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.
 +
}}
 +
  
'''Пример:''' Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
 
 
===Формулировка Задачи===
 
===Формулировка Задачи===
 
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.
 
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.
Строка 132: Строка 165:
 
* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
 
* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
  
* выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;
+
* выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant W</tex>;
  
где <tex> x_i \in (0,1,...,b_i)</tex> для всех <tex> i= 1,2,...,N</tex>.
+
где <tex> x_i \in (0,1,\dots,b_i)</tex> для всех <tex> i= 1,2,\dots,N</tex>.
  
 
===Варианты решения===
 
===Варианты решения===
Строка 148: Строка 181:
 
Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 1 до <tex>W</tex>, по рекуррентной формуле:
 
Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 1 до <tex>W</tex>, по рекуррентной формуле:
  
<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i) </tex> по всем целым <tex> l </tex> из промежутка <tex> 0 \le l \le min(b_i,\lfloor c/w_i \rfloor)</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(c)</tex> вместо двумерного.
Строка 155: Строка 188:
  
 
=== Реализация ===
 
=== Реализация ===
  '''for''' i = 0..W ''<font color="green">// база</font>''
+
  '''for''' i = 0 '''to''' w                              ''<font color="green">//База</font>''
   d[0][i] = 0;
+
   d[0][i] = 0
  '''for''' i = 1..N              
+
  '''for''' i = 1 '''to''' n              
   '''for''' c = 1..W  ''<font color="green">//Перебираем для каждого i, все вместимости </font>''
+
   '''for''' c = 1 '''to''' w                            ''<font color="green">//Перебираем для каждого i, все вместимости </font>''
     d[i][c] = d[i - 1][c];
+
     d[i][c] = d[i - 1][c]
     '''for''' l = min(b[i], c / w[i]) .. 1 ''<font color="green">//ищем l для которого выполняется максимум </font>''
+
     '''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);
+
         d[i][c] =  max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l)
  
 
Сложность алгоритма <tex>O(NW^2)</tex>.
 
Сложность алгоритма <tex>O(NW^2)</tex>.
 
 
==Неограниченный рюкзак==
 
==Неограниченный рюкзак==
 +
{{Задача
 +
|definition =
 
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
 
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
 +
}}
  
'''Пример:''' Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.
 
 
===Формулировка Задачи===
 
===Формулировка Задачи===
 
Каждый предмет может быть выбран любое число раз.
 
Каждый предмет может быть выбран любое число раз.
Строка 175: Строка 209:
 
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
 
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
  
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;
+
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant W</tex>;
  
где <tex> x_i \ge 0 </tex> целое,  для всех <tex> i= 1,2,...,N</tex>.
+
где <tex> x_i \geqslant 0 </tex> целое,  для всех <tex> i= 1,2,\dots,N</tex>.
  
 
===Варианты решения===
 
===Варианты решения===
Строка 185: Строка 219:
  
 
===Метод динамического программирования===
 
===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.
+
Пусть <tex>d(i,c)</tex> - максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.
  
 
Заполним <tex>d(0,c)</tex> нулями.
 
Заполним <tex>d(0,c)</tex> нулями.
Строка 194: Строка 228:
 
d(i,c) =
 
d(i,c) =
 
\begin{cases}
 
\begin{cases}
  d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
+
  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, ..., W;  
+
  \max(d(i - 1, c), d(i, c - w_i) + p_i) & for\ c = w_i, \dots, W;  
 
\end{cases}
 
\end{cases}
 
</tex>
 
</tex>
Строка 203: Строка 237:
 
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:
 
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:
  
<tex>  d(c) = max(d(c), d(c - w_i) + p_i)  </tex>;
+
<tex>  d(c) = \max(d(c), d(c - w_i) + p_i)  </tex>;
  
 
Сложность алгоритма <tex>O(NW)</tex>.
 
Сложность алгоритма <tex>O(NW)</tex>.
  
 
==Непрерывный рюкзак==
 
==Непрерывный рюкзак==
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
+
{{Задача
 +
|definition =
 +
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любую дробную часть от предмета, при этом удельная стоимость сохраняется.
 +
}}
  
'''Пример:''' Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
 
 
===Формулировка Задачи===
 
===Формулировка Задачи===
 
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы
 
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы
Строка 216: Строка 252:
 
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
 
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;
  
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;
+
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant W</tex>;
  
где <tex> 0 \le x_i \le 1</tex> дробное, для всех <tex> i= 1,2,...,N</tex>.
+
где <tex> 0 \leqslant x_i \leqslant 1</tex> дробное, для всех <tex> i= 1,2,\dots,N</tex>.
  
 
===Варианты решения===
 
===Варианты решения===
Строка 224: Строка 260:
  
 
=== Реализация ===
 
=== Реализация ===
  sort(); ''<font color="green">// сортируем в порядке убывания удельной стоимости.</font>''
+
  sort()                       ''<font color="green">//Сортируем в порядке убывания удельной стоимости.</font>''
  '''for''' i = 1..N ''<font color="green">// идем по предметам  </font>''           
+
 
      '''if''' W >= w[i]   ''<font color="green">//если помещается — берем</font>''
+
  '''for''' i = 1 '''to''' n                ''<font color="green">//Идем по предметам  </font>''           
        sum += p[i];
+
  '''if''' w > w[i]                 ''<font color="green">//Если помещается — берем</font>''
        W -= w[i];
+
    sum += p[i]
    '''else'''
+
    w -= w[i]
        sum += W / w[i] * p[i];''<font color="green">// иначе берем сколько можно и выходим</font>''
+
  '''else'''
        '''break''';
+
    sum += w / w[i] * p[i]   ''<font color="green">//Иначе берем сколько можно и выходим</font>''
 +
    '''break'''
  
 
==Задача о суммах подмножеств==
 
==Задача о суммах подмножеств==
'''Задача о суммах подмножеств''' (англ. ''Subset—sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.
+
{{Задача
 +
|definition =
 +
'''Задача о суммах подмножеств''' (англ. ''Subset sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.
 +
}}
  
'''Пример:''' Машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
 
 
===Формулировка Задачи===
 
===Формулировка Задачи===
 
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы
 
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы
Строка 242: Строка 281:
 
*максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_i</tex>;
 
*максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_i</tex>;
  
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</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,...,N</tex>.
+
<tex> x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex>,  для всех <tex> i= 1,2,\dots,N</tex>.
  
 
===Варианты решения===
 
===Варианты решения===
 
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
 
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
 
* Метод динамического программирования.
 
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по дереву. В худшем случае, работает за <tex> O(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>\le c</tex>, подмножества взятого из <tex> 1, ...,\ i</tex> элементов.
+
Пусть <tex>d(i,c)</tex> максимальная сумма  <tex>\leqslant c</tex>, подмножества взятого из <tex> 1, \dots,\ i</tex> элементов.
  
 
Заполним <tex>d(0,c)</tex> нулями.
 
Заполним <tex>d(0,c)</tex> нулями.
Строка 261: Строка 300:
 
d(i,c) =
 
d(i,c) =
 
\begin{cases}
 
\begin{cases}
  d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
+
  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, ..., W;  
+
  \max(d(i - 1, c), d(i - 1, c - w_i) + w_i) & for\ c = w_i, \dots, W;  
 
\end{cases}
 
\end{cases}
 
</tex>
 
</tex>
Строка 271: Строка 310:
  
 
==Задача о размене==
 
==Задача о размене==
 +
{{Задача
 +
|definition =
 
'''Задача о размене''' (англ. ''Change-Making problem'') — имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>.  Нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>.
 
'''Задача о размене''' (англ. ''Change-Making problem'') — имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>.  Нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>.
 +
}}
  
 
Часто задачу ставят как, дать сдачу наименьшим количеством монет.
 
Часто задачу ставят как, дать сдачу наименьшим количеством монет.
Строка 282: Строка 324:
 
*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;
 
*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;
  
Где <tex> x_i \ge 0 </tex> целое,  для всех <tex> i= 1,2,...,N</tex>.
+
Где <tex> x_i \geqslant 0 </tex> целое,  для всех <tex> i= 1,2,\dots,N</tex>.
 
===Варианты решения===
 
===Варианты решения===
 
Самые распространенные методы точного решения это:
 
Самые распространенные методы точного решения это:
Строка 298: Строка 340:
 
d(i,c) =
 
d(i,c) =
 
\begin{cases}
 
\begin{cases}
  d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
+
  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, ..., W;  
+
  min(d(i - 1, c), d(i, c - w_i) + 1) & for\ c = w_i, \dots, W;  
 
\end{cases}
 
\end{cases}
 
</tex>
 
</tex>
Строка 307: Строка 349:
 
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:
 
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:
  
<tex>  d(c) = min(d(c), d(c - w_i) + 1) \qquad  for\ c = w_i, ..., W</tex>.
+
<tex>  d(c) = min(d(c), d(c - w_i) + 1) \qquad  for\ c = w_i, \dots, W</tex>.
  
 
Сложность алгоритма <tex>O(NW)</tex>.
 
Сложность алгоритма <tex>O(NW)</tex>.
  
 
==Задача об упаковке==
 
==Задача об упаковке==
 +
{{Задача
 +
|definition =
 
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') — имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.
 
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') — имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.
 +
}}
  
'''Пример:''' Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.
 
 
===Формулировка Задачи===
 
===Формулировка Задачи===
 
Математически задачу можно представить так:
 
Математически задачу можно представить так:
Строка 320: Строка 364:
 
*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>;
 
*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>;
  
*так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \le Wy_j \qquad j \in {1, ..., N}</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> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен  <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.
Строка 330: Строка 374:
  
 
==Мультипликативный рюкзак==
 
==Мультипликативный рюкзак==
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</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}^M \sum_{j=1}^{N} p_jx_{ij}</tex>
  
так, чтобы <tex>\sum_{i=1}^N w_jx_{ij} \le W_i</tex> выполнялось для всех <tex> i= 1,2,...,N</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,...,N</tex>.
+
<tex>\sum_{j=1}^{M}x_{ij}=1</tex> для всех <tex> i= 1,2,\dots,N</tex>.
  
  
Строка 347: Строка 393:
  
 
==Задача о назначении==
 
==Задача о назначении==
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') — Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le 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>M</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>  соответственно.   
 +
}}
 +
 
 
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
 
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 353: Строка 403:
 
Максимизировать стоимость выбранных предметов <tex>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{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} \le W_i \qquad i=1, \ldots, M</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} \leq 1 \qquad j=1, \ldots, N</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>.
 
<tex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</tex>.
Строка 361: Строка 411:
 
===Варианты решения===
 
===Варианты решения===
 
Применение динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ.
 
Применение динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ.
 +
 +
== См. также ==
 +
* [[Класс NP]]
 +
* [[Метод четырех русских для умножения матриц]]
 +
* [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 +
* [[Meet-in-the-middle]]
  
 
== Источники информации ==
 
== Источники информации ==
Строка 366: Строка 422:
 
*[http://rosettacode.org/wiki/Knapsack_Problem Код для нескольких задач семейства на всевозможных языках]
 
*[http://rosettacode.org/wiki/Knapsack_Problem Код для нескольких задач семейства на всевозможных языках]
 
*[http://www.diku.dk/users/pisinger/95-1.pdf David Pisinger Knapsack problems. — 1995]
 
*[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
 
*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»