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

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

Общим для всех видов является наличие набора из [math]\displaystyle{ n }[/math] предметов, с двумя параметрами — вес [math]\displaystyle{ p_i\gt 0 }[/math] и ценность [math]\displaystyle{ c_i\gt 0 }[/math][math]\displaystyle{ , i= 1,2,...,n }[/math].Есть рюкзак, определенной вместимости [math]\displaystyle{ P }[/math]. Задача — собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака. Обычно все параметры — целые, не отрицательные числа.

Рюкзак 0-1 (англ. 0-1 Knapsack Problem)

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

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

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

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

Каждый предмет [math]\displaystyle{ x_i }[/math] может быть выбран ограниченное число раз. Задача:

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

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

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

Число [math]\displaystyle{ m_i }[/math] называют границей.

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

Каждый предмет [math]\displaystyle{ x_i }[/math] может быть выбран неограниченное число раз. Задача:

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

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

и целое [math]\displaystyle{ x_i \ge 0 }[/math] для всех [math]\displaystyle{ i= 1,2,...,n }[/math].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и [math]\displaystyle{ x_i \ge 0 }[/math] для всех [math]\displaystyle{ i= 1,2,...,n }[/math].

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

Квадратичная задача о ранце представляет собой модификацию классических задач о ранце с ценностью, являющейся квадратичной формой. Пусть [math]\displaystyle{ x = (x_1, .. ,x_n) }[/math] - вектор, задающий, сколько экземпляров каждого предмета окажется в рюкзаке. Задача:

максимизировать [math]\displaystyle{ x^TQx }[/math]

при условиях [math]\displaystyle{ \sum_{i=1}^n p_ix_i \le P }[/math], [math]\displaystyle{ x \in B^n }[/math], или

минимизировать [math]\displaystyle{ x^TQx }[/math]

при условиях [math]\displaystyle{ \sum_{i=1}^n p_ix_i \geq P }[/math], [math]\displaystyle{ x \in B^n }[/math].

При этом [math]\displaystyle{ Q }[/math] — неотрицательно определенная матрица размера [math]\displaystyle{ n \times n }[/math], [math]\displaystyle{ B^n }[/math] задаёт ограничения на количество предметов.

Литература

на русском языке

1. В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий. Прикладные задачи теории графов. — М., 1974. — 232 с.

на английском языке

1. Silvano Martelo, Paolo Toth. Knapsack problems. — Wiley, 1990. — 306 с.
2. David Pisinger. Knapsack problems. — 1995. Архивная копия от 22 декабря 2012 на Wayback Machine

Ссылки

1. Алгоритм рюкзака