Редактирование: Задача о рюкзаке

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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-полных]] задач комбинаторной оптимизации.
  
 
== Реализация ==
 
== Реализация ==
Строка 152: Строка 152:
  
 
=Другие задачи семейства=
 
=Другие задачи семейства=
==Ограниченный рюкзак==
 
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
Строка 158: Строка 157:
 
}}
 
}}
  
 +
== Пример ==
 +
Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
  
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 197: Строка 198:
  
 
Сложность алгоритма <tex>O(NW^2)</tex>.
 
Сложность алгоритма <tex>O(NW^2)</tex>.
==Неограниченный рюкзак==
+
 
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
 
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
 
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
 
}}
 
}}
 +
 +
==Пример==
 +
Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.
  
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 219: Строка 223:
  
 
===Метод динамического программирования===
 
===Метод динамического программирования===
Пусть <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> нулями.
Строка 241: Строка 245:
 
Сложность алгоритма <tex>O(NW)</tex>.
 
Сложность алгоритма <tex>O(NW)</tex>.
  
==Непрерывный рюкзак==
 
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любую дробную часть от предмета, при этом удельная стоимость сохраняется.
+
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
 
}}
 
}}
 +
 +
==Пример==
 +
Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
  
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 270: Строка 276:
 
     '''break'''
 
     '''break'''
  
==Задача о суммах подмножеств==
 
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
'''Задача о суммах подмножеств''' (англ. ''Subset sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.
+
'''Задача о суммах подмножеств''' (англ. ''Subset—sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.
 
}}
 
}}
 +
 +
==Пример==
 +
Машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
  
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 288: Строка 296:
 
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
 
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
 
* Метод динамического программирования.
 
* Метод динамического программирования.
* Использовать различные сложные алгоритмы <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> O(n) </tex>.
  
 
===Метод динамического программирования===
 
===Метод динамического программирования===
Строка 309: Строка 317:
 
Сложность алгоритма <tex>O(NW)</tex>.
 
Сложность алгоритма <tex>O(NW)</tex>.
  
==Задача о размене==
 
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
Строка 353: Строка 360:
 
Сложность алгоритма <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>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.
 
}}
 
}}
 +
 +
==Пример==
 +
Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.
  
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 373: Строка 382:
 
Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ.
 
Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ.
  
==Мультипликативный рюкзак==
 
 
{{Задача
 
{{Задача
 
|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> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
 
}}
 
}}
 +
 +
==Пример==
 +
У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
  
 
===Формулировка Задачи===
 
===Формулировка Задачи===
Строка 392: Строка 403:
 
Применение динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ.
 
Применение динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ.
  
==Задача о назначении==
 
 
{{Задача
 
{{Задача
 
|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> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
  
 
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
 
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
Строка 405: Строка 418:
 
при выполнении условия совместности <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} \leqslant 1 \qquad j=1, \ldots, N</tex>.
+
<tex> \sum_{i=1}^M x_{ij} \leq 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>.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: