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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Общим для всех видов является наличие набора из n предметов, с двумя параметрами — вес  p_i>0 и ценность  c_i>0, i= 1,2,...,n.Есть рюкзак, определенной вместимости P. Задача - собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака. Обычно все параметры целые не отрицательные числа.

Рюкзак 0-1(англ. 0-1 Knapsack Problem)[править | править исходный текст]

Это самая распространенная разновидность рюкзака. Пусть  x_i принимает два значения:  x_i= 1, если груз упакован, и  x_i= 0 в противном случае, где  i= 1,2,...,n. Задача:

максимизировать \sum_{i=1}^n c_ix_i

при наличии ограничения \sum_{i=1}^n p_ix_i \le P на вместимость рюкзака[1][2].

Ограниченный рюкзак(англ. Bounded Knapsack Problem)[править | править исходный текст]

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

максимизировать \sum_{i=1}^n c_ix_i

так чтобы \sum_{i=1}^n p_ix_i \le P выполнялось условие на вместимость

и  x_i \in (0,1,...,m_i) для всех  i= 1,2,...,n[3].

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

Неограниченный рюкзак (целочисленный рюкзак)(англ. Unbounded Knapsack Problem (integer knapsack))[править | править исходный текст]

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

максимизировать \sum_{i=1}^n c_ix_i

так чтобы \sum_{i=1}^n p_ix_i \le P выполнялось условие на вместимость

и целое  x_i \ge 0 для всех  i= 1,2,...,n[4].

Рюкзак с мультивыбором(англ. Multiple-choice Knapsack Problem)[править | править исходный текст]

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

максимизировать \sum_{i=1}^n \sum_{j\in S_i} c_{ij}x_{ij}

так чтобы \sum_{i=1}^n \sum_{j\in S_i} p_{ij}x_{ij} \le P выполнялось условие на вместимость,

\sum_{j\in S_i}x_{ij}=1 для всех  i= 1,2,...,n

Мультипликативный рюкзак(англ. Multiple Knapsack Problem)[править | править исходный текст]

Пусть у нас есть n предметов и m рюкзаков (m\le n). У каждого предмета, как и раньше, есть вес  p_j>0 и ценность  c_j>0 j= 1,2,...,n, у каждого рюкзака соответственно своя вместимость P_i i= 1,2,...,m. x_i \in {0,1}Задача:

максимизировать \sum_{i=1}^m \sum_{j=1}^{n} c_{ij}x_{ij}

так чтобы \sum_{i=1}^n p_{j}x_{ij} \le P_i выполнялось условие для всех  i= 1,2,...,n,

\sum_{j=1}^{m}x_{ij}=1 для всех  i= 1,2,...,n[5].

Многомерный рюкзак(англ. Multy-dimensional knapsack problem)[править | править исходный текст]

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

максимизировать \sum_{i=1}^n c_ix_i

так чтобы \sum_{i=1}^n p_{ij}x_i \le P_j,  j= 1,2,...,m

и  x_i \ge 0 для всех  i= 1,2,...,n[4].

Примечания[править | править исходный текст]

  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

Литература[править | править исходный текст]

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