Задача упаковки рюкзака

Задача упаковки рюкзака: Как подобрать коробки так, чтобы их стоимость была максимальной, а суммарный вес не более 15 кг?

Задача упаковки рюкзака ( англ. Knapsack problem ) - Задача комбинаторной оптимизации. Задача состоит в наполнены рюкзака, который способен выдержать некоторую максимальную массу, предметами, каждый из которых имеет стоимость (или полезность) и массу. Необходимо выбрать объекты таким образом, чтобы максимизировать суммарную стоимость (или пользу), но не превысить максимально допустимую массу.


1. История

1.1. Исследования

Задача упаковки рюкзака является одной из 21 NP-полных задач Ричарда Карпа ( англ. Richard Karp ) Изложенных в его статье 1972 года. Интенсивное исследование проблемы началось с середины ХХ века но известное упоминание еще ​​в 1897 году, в статье Джорджа Мэтьюза Балларда [1]. Описание задачи достаточно простое, но решение - сложное. Существующие алгоритмы, на практике, способны решить задачи достаточно больших размеров. Однако, уникальная структура задачи, а также тот факт, что она присутствует как подзадача в больших, общих проблемах, делает ее важной для научных исследований.


2. Применение

Задача упаковки рюкзака используется для моделирования различных проблем, в частности:

  • В системах поддержки управления портфелем для балансировки и диверсификации выбранных капиталовложений с целью поиска наилучшего баланса между рисками и эффективностью вкладов в различные финансовые активы;
  • При загрузке лодки или самолета : выбор багажей для оптимальной загрузки транспортного зособив;
  • В кройке различных материалов (ткани, стальные листы и т.д.): выбор оптимальной схемы раскроя материалов с целью уменьшения количества отходов.

Также исследование этой задачи полезно для поиска решений методом генерирования столбцов и в задаче загрузки контейнеров.

Задача происходит от ситуации, когда путешественник оказывается перед выбором предметов, необходимо взять в путешествие: следует выбрать самое, но не перегрузить рюкзак.


3. Постановка задачи

Задачу упаковки рюкзака можно определить средствами математического аппарата. Пусть каждому объекту для упаковки сопоставлены индекс i, который принимает значения от 1 до n. Числа w_i и p_i соответствуют весу и стоимости объекта i. Максимальная допустимая масса, которую способен выдержать рюкзак, равна W.

0-1 задача упаковки рюкзака

Существует много вариантов заполнения рюкзака. Для описания отдельного варианта упаковки необходимо указать для каждого объекта, избран (упаковано). Для этого можно использовать двоичный вектор X = (x_1, x_2, \ dots, x_n) , Компонента x_i которого равен 1, если i-тый объект запаковано, и 0 если нет. Этот вектор называется вектором заполнения. Вес и стоимость упакованных предметов, можно вычислить как функцию от вектора заполнения.

Для заданного вектора заполнения X стоимость предметов упакованных в рюкзак равна:

z (X) = \ sum_ {\ {i, \, x_i = 1 \}} p_i = \ sum_ {i = 1} ^ n x_ip_i

Аналогично, общая масса предметов равна:

w (X) = \ sum_ {i = 1} ^ n x_iw_i

Таким образом, задача упаковки рюкзака заключается в отыскании такого вектора заполнения X = (x_1, x_2, \ dots, x_n) , Которая максимизирует функцию z (X) при условии:

w (X) = \ sum_ {i = 1} ^ n x_iw_i \ le W (1)

То есть, общая масса выбранных предметов w (X) не превышает возможности рюкзака W .

Вообще, действуют следующие дополнительные условия:

  • \ Sum_ {i = 1} ^ n w_i> W : Все доступные объекты невозможно положить в рюкзак вместе;
  • p_i> 0, \ forall i \ in \ {1, \ dots, n \} : Любой дополнительный объект предпочитает;
  • w_i> 0, \ forall i \ in \ {1, \ dots, n \} : Любой объект использует ресурсы.

Терминология:

  • Функция z (X) - Называется целевой;
  • Любой вектор X , Что соответствует условию (1), называется допустимым;
  • Если стоимость z (X) максимальная, то вектор X называется оптимальным.

Предположим, кроме стоимости предметы имеют еще одну характеристику (например, плотность). Задача поиска вектора заполнения X , Который максимизирует обе функции (суммарная стоимость и суммарная плотность) является многокритериальным вариантом 0-1 задачи упаковки рюкзака. [2]

Ограниченная задача упаковки рюкзака ограничивает количество x_i копий каждого вида предмета максимальным целым значением k_i . Математически эту задачу можно сформулировать так:

  • максимизировать \ Qquad \ sum_ {i = 1} ^ n p_ix_i
  • при \ Qquad \ sum_ {i = 1} ^ n w_ix_i \ leqslant W, \ quad \ quad x_i \ in \ {0,1, \ ldots, k_i \}

Неограниченное задача упаковки ранца (НЗПР) не накладывает верхнего предела для количества копий каждого вида предмета.

Особый интерес представляет частный случай задачи упаковки рюкзака с такими свойствами:

  • она является проблемой выбора,
  • она является 0-1 задачей,
  • для каждого вида предмета вес равен стоимости: w_i = p_i .

В этом случае задача эквивалентна такой задачи: задано множество неотрицательных целых чисел, существует любая ее подмножество, сумма элементов которой составляет точно W? Или, если допускается отрицательная вес и W равна нулю, то задачей является: задано множество целых чисел, существует непустое подмножество, сумма элементов которой точно равна 0? Этот частный случай называется задачей суммы подмножества. В области криптографии термин задача упаковки рюкзака часто используется для обозначения конкретно задачи суммы подмножества.

Если допускается несколько рюкзаков, то задачу лучше рассматривать как задачу упаковки в контейнеры.


3.1. Формулировка средствами теории множеств

Задачу упаковки рюкзака можно описать средствами теории множеств. [3]

Пусть заданы множество объектов U , Вес w (u) \ in Z ^ + , И стоимость z (u) \ in Z ^ + для каждого объекта u \ in U и максимальную допустимый вес W . Необходимо найти подмножество U ' , Такую, чтобы:

\ Sum_ {u \ in U '} w (u) \ le W и \ Sum_ {u \ in U '} p (u) = max .

4. NP-сложность

В контексте исследования алгоритмической сложности задачи, ее оптимизационное формулировки меняют на задачу распознавания. Представление в виде задачи распознавания вводит дополнительный параметр P - желаемая стоимость предметов в рюкзаке и ставит вопрос, существует еще один вариант упаковки, с суммарной стоимостью упакованных предметов больше P. [ 3] Цель введения задачи распознавания состоит в том, что с точки зрения теории вычислительной сложности и NP-полноты для нее легче определять сложность. Если целевую функцию не сложно вычислять, то задача распознавания не сложнее соответствующую задачу оптимизации. Таким образом, с NP-полноты задачи распознавания следует NP-полнота задачи оптимизации. [4] [3]

Задача распознавания для оптимизационной задачи 0-1 упаковки рюкзака формулируется так: Задан конечное множество U объектов, вес w (u) \ in Z ^ + , Стоимость z (u) \ in Z ^ + для каждого объекта u \ in U и целые числа W (емкость рюкзака) и P (желательно стоимость). Существует такая подмножество U ' , Что:

\ Sum_ {u \ in U '} w (u) \ le W , И \ Sum_ {u \ in U '} z (u) \ ge P ?

5. Приближенные методы решения

Как и для других NP-полных задач, в некоторых случаях достаточно найти решение, приближенное к оптимальному, но не обязательно оптимальное. Желательно также, чтобы разница между оптимальным решением и найденным была гарантированных размеров.

Далее под эффективностью предмета понимается отношение его стоимости к весу. Чем выше эффективность предмета, тем полезнее он для упаковки.

5.1. Жадный алгоритм

Две фазы жадного алгоритма: Слева: благоустройство предметов за их эффективностью (в этом случае стоимость на кило веса). Справа: упаковка в рюкзак, если есть возможность. Полученный решение дает $ 11 и 11 кг, в то время как оптимальный $ 12 и 14 кг.

Одним из простейших алгоритмов поиска приблизительного решения является жадный алгоритм. Идея алгоритма заключается в том, чтобы класть в рюкзак в первую очередь эффективные предметы, вплоть до его заполнения:

 упорядочить предметы в убывающем порядке эффективности w_пак: = 0 
 для i от 1 до n если w [i] + w_пак <= W тогда x [i]: = 1 w_пак: = w_пак + w [i] иначе x [i] = 0 конец если конец для 



6. Точные методы

Классическая задача упаковки рюкзака была изучена достаточно глубоко. Сегодня существует много методов поиска точных решений задачи. Большинство из них являются улучшенными вариантами одного из следующих методов поиска точного решения задачи.

6.1. Динамическое программирование

Задача упаковки рюкзака имеет свойство суб-оптимальной структуры, т.е. существует возможность найти оптимальное решение задачи по i переменными на основе решения задачи по i-1 переменными. Это свойство позволяет применение средств динамического программирования для решения задачи упаковки рюкзака.

Пусть требуется решить 0-1 задачу упаковки рюкзака. Обозначим через KP (i, c) максимальную стоимость первых i предметов с общим весом меньше или равной c. Надо найти KP (n, W).

Идея состоит в том, что оптимальное решение задачи KP (i, c) можно получить, используя решения двух простых задач:

  • задачи с i-1 переменными для рюкзака с такой же емкостью c (KP (i-1, c)), и x_i = 0 ;
  • задачи с i-1 переменными для рюкзака с емкостью c - w_i ( KP (i-1, c - w_i) ) И x_i = 1 .

Решение задачи упаковки рюкзака с 0 переменными (KP (0, *)) равна нулю. Решение задачи упаковки рюкзака при c = 0 (KP (*, 0)) также равен нулю.

Теперь можно записать KP (i, c) рекурсивно:

  • KP (0, \, c) = 0, \ quad 0 \ le c \ le W
  • KP (i, \, 0) = 0, \ quad 0 \ le i \ le n
  • KP (i, \, c) = KP (i-1, \, c) , Если w_i> c \, \! (Новый предмет тяжелее, чем текущий резерв веса)
  • KP (i, \, c) = \ max (KP (i-1, \, c), \, KP (i-1, c-w_i) + p_i) , Если w_i \ leqslant c .

Затем строится таблица T [i, c], элементы которой содержат значения решений задач KP (i, c) в следующий способ:

 для c от 0 до W делать T [0, c] = 0 конец для 
 для i от 1 до n делать для c от 0 до W делать если c> = w [i] то T [i, c] = max (T [i-1, c], T [i-1, cw [ i]] + p [i]) иначе T [i, c] = T [i-1, c] конец если конец для конец для вывести T [n, W] 

Когда таблица построена, случай задачи T [n, W] следует свести к случаю T [0, *].

Временная сложность этого алгоритма равна O (nW) . Алгоритм имеет два преимущества:

  1. Скорость;
  2. Не требуется сортировка переменных.

и недостаток:

  1. требует сравнительно много памяти (что делает его неприемлемым для решения больших задач).

Этот метод был разработан Робертом Гарфинкель и Джорджем Немгаузером в 1972 году. [5]


6.2. Метод ветвей и границ

Подобно другим задач комбинаторной оптимизации, задача упаковки рюкзака может быть решена методом ветвей и границ ( англ. Branch-and-bound algorithm ). Применение метода ветвей и границ к решению задачи упаковки рюкзака впервые предложил Колесар в 1967 году. Вариант алгоритма разработан Гринбергом и Хегеричем в 1970 году имел существенно более низкие требования к памяти и времени. Горовиц и Сане в 1974 году предложили свой алгоритм построен на основе предыдущих вариантов. Этот алгоритм эффективный и самый простой для реализации по сравнению с предыдущими алгоритмами. Предложенный Мартэло и тозом алгоритм [6] широко распространен. Преимуществом этого метода являются низкие требования к объему требуемой памяти.


См.. также

Nuvola apps edu mathematics blue-p.svg
В Википедии есть портал

Примечания

  1. (Англ.) GB Mathews, On the partition of numbers, Proceedings of the London Mathematical Society, 28:486-490, 1897.
  2. Matthias Ehrgott Multicriteria Optimization. - Springer, 2005. ISBN 3-540-21398-8.
  3. а б в (Англ.) Michail G. Lagoudakis, The 0-1 Knapsack Problem - An Introductory Survey - www2.isye.gatech.edu / ~ mlagouda / acadpape.html, 1996.
  4. Garey MR, Johnson DS, Computers and Intractability: A Guide to the Theory of NP-completeness, WH Freeman and Comp., San Francisco, 1979.
  5. (Англ.) RS Garfinkel et GL Nemhauser. Integer Pogramming. John Wiley & Sons, New York, 1972. ISBN 0-471-29195-1.
  6. (Англ.) Silvano Martello et Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990 ISBN 0471924202.
  • (Англ.) Hans Kellerer, Ulright Pferschy and David Pisinger, Knapsack Problems, Springer, 2004 ISBN 3-540-40286-1.
  • (Англ.) Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., Pp. 163-166, 1985.