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

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

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

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

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

максимизировать ∑ i = 1 n c i x i {displaystyle sum _{i=1}^{n}c_{i}x_{i}}

при наличии ограничения ∑ i = 1 n p i x i ≤ P {displaystyle sum _{i=1}^{n}p_{i}x_{i}leq P} на вместимость рюкзака.

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

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

максимизировать ∑ i = 1 n c i x i {displaystyle sum _{i=1}^{n}c_{i}x_{i}}

так, чтобы ∑ i = 1 n p i x i ≤ P {displaystyle sum _{i=1}^{n}p_{i}x_{i}leq P} выполнялось условие на вместимость

и x i ∈ ( 0 , 1 , . . . , m i ) {displaystyle x_{i}in (0,1,...,m_{i})} для всех i = 1 , 2 , . . . , n {displaystyle i=1,2,...,n} .

Число m i {displaystyle m_{i}} называют границей.

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

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

максимизировать ∑ i = 1 n c i x i {displaystyle sum _{i=1}^{n}c_{i}x_{i}}

так, чтобы ∑ i = 1 n p i x i ≤ P {displaystyle sum _{i=1}^{n}p_{i}x_{i}leq P} выполнялось условие на вместимость

и целое x i ≥ 0 {displaystyle x_{i}geq 0} для всех i = 1 , 2 , . . . , n {displaystyle i=1,2,...,n} .

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

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

максимизировать ∑ i = 1 n ∑ j ∈ S i c i j x i j {displaystyle sum _{i=1}^{n}sum _{jin S_{i}}c_{ij}x_{ij}}

так, чтобы ∑ i = 1 n ∑ j ∈ S i p i j x i j ≤ P {displaystyle sum _{i=1}^{n}sum _{jin S_{i}}p_{ij}x_{ij}leq P} выполнялось условие на вместимость,

∑ j ∈ S i x i j = 1 {displaystyle sum _{jin S_{i}}x_{ij}=1} для всех i = 1 , 2 , . . . , n {displaystyle i=1,2,...,n}

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

Пусть у нас есть n {displaystyle n} предметов и m {displaystyle m} рюкзаков ( m ≤ n {displaystyle mleq n} ). У каждого предмета, как и раньше, есть вес p j > 0 {displaystyle p_{j}>0} и ценность c j > 0 {displaystyle c_{j}>0} j = 1 , 2 , . . . , n {displaystyle j=1,2,...,n} , у каждого рюкзака соответственно своя вместимость P i {displaystyle P_{i}} при i = 1 , 2 , . . . , m {displaystyle i=1,2,...,m} . x i ∈ 0 , 1 {displaystyle x_{i}in {0,1}} . Задача:

максимизировать ∑ i = 1 m ∑ j = 1 n c j x i j {displaystyle sum _{i=1}^{m}sum _{j=1}^{n}c_{j}x_{ij}}

так, чтобы ∑ i = 1 n p j x i j ≤ P i {displaystyle sum _{i=1}^{n}p_{j}x_{ij}leq P_{i}} выполнялось условие для всех i = 1 , 2 , . . . , m {displaystyle i=1,2,...,m} ,

∑ j = 1 m x i j ≤ 1 {displaystyle sum _{j=1}^{m}x_{ij}leq 1} для всех i = 1 , 2 , . . . , n {displaystyle i=1,2,...,n} .

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

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

максимизировать ∑ i = 1 n c i x i {displaystyle sum _{i=1}^{n}c_{i}x_{i}}

так, чтобы ∑ i = 1 n p i j x i ≤ P j {displaystyle sum _{i=1}^{n}p_{ij}x_{i}leq P_{j}} , j = 1 , 2 , . . . , m {displaystyle j=1,2,...,m}

и x i ≥ 0 {displaystyle x_{i}geq 0} для всех i = 1 , 2 , . . . , n {displaystyle i=1,2,...,n} .

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

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

максимизировать x T Q x {displaystyle x^{T}Qx}

при условиях ∑ i = 1 n p i x i ≤ P {displaystyle sum _{i=1}^{n}p_{i}x_{i}leq P} , x ∈ B n {displaystyle xin B^{n}} , или

минимизировать x T Q x {displaystyle x^{T}Qx}

при условиях ∑ i = 1 n p i x i ≥ P {displaystyle sum _{i=1}^{n}p_{i}x_{i}geq P} , x ∈ B n {displaystyle xin B^{n}} .

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