1
правка
Изменения
м
Вор грабит склад'''Ограниченный рюкзак''' (англ. Он ''Bounded Knapsack Problem'') — обобщение классической задачи, когда любой предмет может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную суммубыть взят некоторое количество раз.
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
Перекупщик закупается на оптовой базе'''Неограниченный рюкзак''' (англ. Он ''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может увезти ограниченное количество товара, быть выбран любое количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную суммураз.
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
Вор грабит мясника'''Непрерывный рюкзак''' (англ. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любую дробную часть от предмета, при этом удельная стоимость сохраняется.
'''Задача о суммах подмножеств''' (англ. ''Subset—sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.
Машина может увезти определенное количество груза'''Задача о суммах подмножеств''' (англ. Нужно увезти как можно больше крупного неделимого мусора за раз''Subset sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') — имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <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> соответственно.
Выбрать '''Задача о назначении''' (англ. ''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> соответственно.
→Метод динамического программирования
* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.
* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}*{N}) </tex>
* Метод динамического программирования. Сложность — <tex>O(N*WNW)</tex>.
== Метод динамического программирования ==
Пусть <tex>A(k, s)</tex> есть максимальная стоимости стоимость предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,\dots,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>.
<tex>A(k, 0) = 0</tex>
Заметим, что при построении <tex>A</tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w)</tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит.
Метод динамического программирование всё равно не повзволяет позволяет решать задачу за полиномиальное время, потому что задача его сложность зависит от максимального веса. Задача о ранце (или задача о рюкзаке) — одна из [[Класс NP|NP-полных]] задач комбинаторной оптимизации.
== Реализация ==
Сначала генерируем <tex>A</tex>.
'''for''' i = 0 '''to W''' w
A[0][i] = 0
'''for''' i = 0 '''to N''' n A[i][0] = 0 ''<font color="green">// Первые элементы приравниваем к 0</font>'' '''for''' k = 1 '''to N ''' n '''for''' s = 1 '''to W ''' w ''<font color="green">//Перебираем для каждого k все вместимости</font>'' '''if''' s >= w[k] ''<font color="green">//Если текущий предмет вмещается в рюкзак</font>'' A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]) ''<font color="green">//выбираем Выбираем класть его или нет</font>''
'''else'''
A[k][s] = A[k-1][s] ''<font color="green">//иначеИначе, не кладем</font>''
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
'''function''' findAns('''int''' k, '''int''' s)
'''if''' A[k][s] == 0
'''return'''
'''if''' A[k-1][s] == A[k][s] findAns(k-1, s)
'''else'''
findAns(k-1, s - w[k])
ans.push(k)
Сложность алгоритма <tex>O(N*WNW)</tex>
== Пример ==
'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''
Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ. Будем идти в обратном порядке по <tex>k</tex>. ''<font color="red000000">Красным обозначен фоном обозначим наш путь</font>''
{|border="1" class="wikitable" style="text-align:center" width="75%"
=Другие задачи семейства=
==Ограниченный рюкзак =='''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.
{{Задача
|definition =
}}
===Формулировка Задачи===
Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 1 до <tex>W</tex>, по рекуррентной формуле:
<tex>d(i,c) = \max(d(i, c), d(i - 1, c - lw_i) + lp_i) </tex> по всем целым <tex> l </tex> из промежутка <tex> 0 \leqslant l \leqslant min(b_i,\lfloor c/w_i \rfloor)</tex>.
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.
=== Реализация ===
'''for''' i = 0 '''to W ''' w ''<font color="green">// базаБаза</font>''
d[0][i] = 0
'''for''' i = 1 '''to N ''' n '''for''' c = 1 '''to W ''' w ''<font color="green">//Перебираем для каждого i, все вместимости </font>''
d[i][c] = d[i - 1][c]
'''for''' l = min(b[i], c / w[i]) to '''downto''' 1 ''<font color="green">//ищем Ищем l для которого выполняется максимум </font>''
d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l)
Сложность алгоритма <tex>O(N*WNW^2)</tex>.
==Неограниченный рюкзак==
{{Задача
|definition =
}}
===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> - максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.
Заполним <tex>d(0,c)</tex> нулями.
==Непрерывный рюкзак==
{{Задача
|definition =
}}
=== Реализация ===
sort() ''<font color="green">// сортируем Сортируем в порядке убывания удельной стоимости.</font>'' '''for''' i = 1 '''to N ''' n ''<font color="green">// идем Идем по предметам </font>'' '''if''' W w > w[i] ''<font color="green">//если Если помещается — берем</font>'' sum += p[i] W w -= w[i] '''else''' sum += W w / w[i] * p[i] ''<font color="green">// иначе Иначе берем сколько можно и выходим</font>'' '''break'''
==Задача о суммах подмножеств==
{{Задача
|definition =
}}
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по деревуИспользовать различные сложные алгоритмы <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><texref> OKoiliaris, Konstantinos; Xu, Chao (n2015-07-08) . "A Faster Pseudopolynomial Time Algorithm for Subset Sum".</ref><ref>Bringmann K. A near-linear pseudopolynomial time algorithm for subset sum[C]//Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2017: 1073-1084</texref>.
===Метод динамического программирования===
==Задача об упаковке==
{{Задача
|definition =
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') — имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно вывезти из шахты распределить все куски рудыпредметы, используя наименьшее число вагонетокзадействовав минимальное количество рюкзаков.
}}
==Мультипликативный рюкзак==
{{Задача
|definition =
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У транспортной компании есть парк машин разной грузоподъемностикаждого рюкзака своя вместимость <tex>W_i</tex>. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременноЗадача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
}}
==Задача о назначении==
{{Задача
|definition =
}}
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
===Формулировка Задачи===
при выполнении условия совместности <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 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>.