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

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
м (rollbackEdits.php mass rollback)
 
(не показано 35 промежуточных версий 9 участников)
Строка 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}}*{N}) </tex>
+
* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}{N}) </tex>
  
* Метод динамического программирования. Сложность — <tex>O(N*W)</tex>.
+
* Метод динамического программирования. Сложность — <tex>O(NW)</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, 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>
Строка 56: Строка 56:
 
Заметим, что при построении <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 to W
+
  '''for''' i = 0 '''to''' w
 
   A[0][i] = 0
 
   A[0][i] = 0
  '''for''' i = 0 to 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 to N                
+
  '''for''' k = 1 '''to''' n                
   '''for''' s = 1 to 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*W)</tex>
+
Сложность алгоритма <tex>O(NW)</tex>
  
 
== Пример ==
 
== Пример ==
Строка 126: Строка 126:
 
'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''
 
'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''
  
Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ. Будем идти в обратном порядке по <tex>k</tex>. ''<font color="red">Красным обозначен наш путь</font>''
+
Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ. Будем идти в обратном порядке по <tex>k</tex>. ''<font color="000000">Красным фоном обозначим наш путь</font>''
  
 
{|border="1" class="wikitable" style="text-align:center" width="75%"
 
{|border="1" class="wikitable" style="text-align:center" width="75%"
Строка 147: Строка 147:
 
Таким образом, в набор входит <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>
  
 
=Другие задачи семейства=
 
=Другие задачи семейства=
==Ограниченный рюкзак ==
+
==Ограниченный рюкзак==
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.
 
 
 
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
+
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.
 
}}
 
}}
 +
  
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 182: Строка 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 \leqslant l \leqslant 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> вместо двумерного.
Строка 189: Строка 188:
  
 
=== Реализация ===
 
=== Реализация ===
  '''for''' i = 0 to 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 to N              
+
  '''for''' i = 1 '''to''' n              
   '''for''' c = 1 to 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]) to 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(N*W^2)</tex>.
+
Сложность алгоритма <tex>O(NW^2)</tex>.
 
 
 
==Неограниченный рюкзак==
 
==Неограниченный рюкзак==
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
 
 
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.
+
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
 
}}
 
}}
  
Строка 223: Строка 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> нулями.
Строка 246: Строка 242:
  
 
==Непрерывный рюкзак==
 
==Непрерывный рюкзак==
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
 
 
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
+
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любую дробную часть от предмета, при этом удельная стоимость сохраняется.
 
}}
 
}}
  
Строка 266: Строка 260:
  
 
=== Реализация ===
 
=== Реализация ===
  sort()                         ''<font color="green">// сортируем в порядке убывания удельной стоимости.</font>''
+
  sort()                       ''<font color="green">//Сортируем в порядке убывания удельной стоимости.</font>''
  '''for''' i = 1 to 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 =
 
|definition =
Машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
+
'''Задача о суммах подмножеств''' (англ. ''Subset sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.
 
}}
 
}}
  
Строка 295: Строка 288:
 
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
 
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
 
* Метод динамического программирования.
 
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по дереву. В худшем случае, работает за <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>.
  
 
===Метод динамического программирования===
 
===Метод динамического программирования===
Строка 361: Строка 354:
  
 
==Задача об упаковке==
 
==Задача об упаковке==
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') — имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.
 
 
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.
+
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') — имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.
 
}}
 
}}
  
Строка 383: Строка 374:
  
 
==Мультипликативный рюкзак==
 
==Мультипликативный рюкзак==
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
 
 
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
+
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
 
}}
 
}}
  
Строка 404: Строка 393:
  
 
==Задача о назначении==
 
==Задача о назначении==
'''Задача о назначении''' (англ. ''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>  соответственно. 
 
 
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
Выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
+
'''Задача о назначении''' (англ. ''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>  соответственно.
 
}}
 
}}
 +
 
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
 
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 417: Строка 405:
 
при выполнении условия совместности <tex>\sum_{j=1}^N w_{ij} x_{ij} \leqslant 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>.

Текущая версия на 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»