Список задач о рюкзаке

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Список задач о ранце»)
Перейти к навигации Перейти к поиску

Задача о рюкзаке (или ранце) — это одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Поэтому у задачи существует несколько разновидностей.

Общим для всех видов является наличие набора из предметов, с двумя параметрами — вес и ценность .Есть рюкзак, определенной вместимости . Задача — собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака. Обычно все параметры — целые, не отрицательные числа.

Это самая распространенная разновидность рюкзака. Пусть принимает два значения: , если груз упакован, и в противном случае, где . Задача:

максимизировать

при наличии ограничения на вместимость рюкзака[1][2].

Ограниченный рюкзак (англ. Bounded Knapsack Problem)

[править | править код]

Каждый предмет может быть выбран ограниченное число раз. Задача:

максимизировать

так, чтобы выполнялось условие на вместимость

и для всех [3].

Число называют границей[3].

Неограниченный рюкзак (целочисленный рюкзак) (англ. Unbounded Knapsack Problem (integer knapsack))

[править | править код]

Каждый предмет может быть выбран неограниченное число раз. Задача:

максимизировать

так, чтобы выполнялось условие на вместимость

и целое для всех [4].

Рюкзак с мультивыбором (англ. Multiple-choice Knapsack Problem)

[править | править код]

Все предметы разделяют на классов . Обязательным является условие выбора только одного предмета из каждого класса. принимает значение только 0 и 1. Задача:

максимизировать

так, чтобы выполнялось условие на вместимость,

для всех

Мультипликативный рюкзак (англ. Multiple Knapsack Problem)

[править | править код]

Пусть у нас есть предметов и рюкзаков (). У каждого предмета, как и раньше, есть вес и ценность , у каждого рюкзака соответственно своя вместимость при . . Задача:

максимизировать

так, чтобы выполнялось условие для всех ,

для всех [5].

Многомерный рюкзак (англ. Multi-dimensional knapsack problem)

[править | править код]

Если есть более одного ограничения на рюкзак, например объем и вес, задачу называют m-мерной задачей о ранце. Например, для не ограниченного варианта:

максимизировать

так, чтобы ,

и для всех [4].

Квадратичная задача о рюкзаке (англ. Quadratic knapsack problem)

[править | править код]

Квадратичная задача о ранце представляет собой модификацию классических задач о ранце с ценностью, являющейся квадратичной формой. Пусть - вектор, задающий, сколько экземпляров каждого предмета окажется в рюкзаке. Задача:

максимизировать

при условиях , , или

минимизировать

при условиях , .

При этом — неотрицательно определенная матрица размера , задаёт ограничения на количество предметов[6].

Примечания

[править | править код]
  1. Бурков, 1974, p. 217.
  2. Silvano, 1990, p. 2.
  3. 1 2 Pisinger, 1995, p. 127.
  4. 1 2 Pisinger, 1995, p. 147.
  5. Silvano, 1990, p. 157.
  6. G. Gallo, P. L. Hammer, B. Simeone. Quadratic knapsack problems (англ.) // Mathematical Programming Studies. — 2009. — 24 февраль (vol. 12). — P. 132-149. — ISSN 0303-3929. Архивировано 24 октября 2016 года.

Литература

[править | править код]
на русском языке
  1. В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий. Прикладные задачи теории графов. — М., 1974. — 232 с.
на английском языке
  1. Silvano Martelo, Paolo Toth. Knapsack problems. — Wiley, 1990. — 306 с.
  2. David Pisinger. Knapsack problems. — 1995. Архивная копия от 22 декабря 2012 на Wayback Machine
  1. Алгоритм рюкзака