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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
м (rollbackEdits.php mass rollback)
 
(не показано 28 промежуточных версий 9 участников)
Строка 23: Строка 23:
 
== Метод динамического программирования ==
 
== Метод динамического программирования ==
  
Пусть <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> предметов, входящих в рюкзак, рекурсивной функцией:
Строка 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%"
Строка 152: Строка 152:
  
 
=Другие задачи семейства=
 
=Другие задачи семейства=
 +
==Ограниченный рюкзак==
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
Строка 157: Строка 158:
 
}}
 
}}
  
== Пример ==
 
Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
 
  
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 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(NW^2)</tex>.
 
Сложность алгоритма <tex>O(NW^2)</tex>.
 
+
==Неограниченный рюкзак==
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
 
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
 
'''Неограниченный рюкзак''' (англ.''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> нулями.
Строка 245: Строка 241:
 
Сложность алгоритма <tex>O(NW)</tex>.
 
Сложность алгоритма <tex>O(NW)</tex>.
  
 +
==Непрерывный рюкзак==
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
+
'''Непрерывный рюкзак''' (англ. ''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>''
 
        sum += p[i]
 
        W -= w[i]
 
    '''else'''
 
        sum += W / w[i] * p[i]  ''<font color="green">// иначе берем сколько можно и выходим</font>''
 
        '''break'''
 
  
 +
'''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 =
 
|definition =
'''Задача о суммах подмножеств''' (англ. ''Subset—sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.
+
'''Задача о суммах подмножеств''' (англ. ''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>.
  
 
===Метод динамического программирования===
 
===Метод динамического программирования===
Строка 316: Строка 309:
 
Сложность алгоритма <tex>O(NW)</tex>.
 
Сложность алгоритма <tex>O(NW)</tex>.
  
 +
==Задача о размене==
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
Строка 359: Строка 353:
 
Сложность алгоритма <tex>O(NW)</tex>.
 
Сложность алгоритма <tex>O(NW)</tex>.
  
 +
==Задача об упаковке==
 
{{Задача
 
{{Задача
 
|definition =
 
|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>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.
 
}}
 
}}
 
==Пример==
 
Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.
 
  
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 381: Строка 373:
 
Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ.
 
Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ.
  
 +
==Мультипликативный рюкзак==
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
 
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
 
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
 
}}
 
}}
 
==Пример==
 
У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
 
  
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 402: Строка 392:
 
Применение динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ.
 
Применение динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ.
  
 +
==Задача о назначении==
 
{{Задача
 
{{Задача
 
|definition =
 
|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>  соответственно.   
 
'''Задача о назначении''' (англ. ''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>M</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»