1
правка
Изменения
м
== Пример ==
Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
==Пример==
Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.
==Пример==
Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
sum += w / w[i] * p[i] ''<font color="green">//Иначе берем сколько можно и выходим</font>'' '''break'''
==Пример==
Машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
==Пример==
Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.
==Пример==
У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
==Пример==
Выбрать <tex>M</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(5, 13)</tex> восстанавливаем ответ. Будем идти в обратном порядке по <tex>k</tex>. ''<font color="red000000">Красным обозначен фоном обозначим наш путь</font>''
{|border="1" class="wikitable" style="text-align:center" width="75%"
=Другие задачи семейства=
==Ограниченный рюкзак==
{{Задача
|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> вместо двумерного.
Сложность алгоритма <tex>O(NW^2)</tex>.
==Неограниченный рюкзак==
{{Задача
|definition =
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
}}
===Формулировка Задачи===
===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> - максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.
Заполним <tex>d(0,c)</tex> нулями.
Сложность алгоритма <tex>O(NW)</tex>.
==Непрерывный рюкзак==
{{Задача
|definition =
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любою любую дробную часть от предмета, при этом удельная стоимость сохраняется.
}}
===Формулировка Задачи===
=== Реализация ===
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'''
==Задача о суммах подмножеств==
{{Задача
|definition =
'''Задача о суммах подмножеств''' (англ. ''Subset—sum Subset sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.
}}
===Формулировка Задачи===
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по деревуИспользовать различные сложные алгоритмы <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>.
===Метод динамического программирования===
Сложность алгоритма <tex>O(NW)</tex>.
==Задача о размене==
{{Задача
|definition =
Сложность алгоритма <tex>O(NW)</tex>.
==Задача об упаковке==
{{Задача
|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 =
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') — Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>, у <tex> j </tex> предмета <tex> p_{ij} </tex> стоимость и вес, при помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответственно.
}}
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
при выполнении условия совместности <tex>\sum_{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>.
