Русская Википедия:Список задач о рюкзаке
Задача о рюкзаке (или ранце) — это одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Поэтому у задачи существует несколько разновидностей.
Общим для всех видов является наличие набора из <math>n</math> предметов, с двумя параметрами — вес <math> p_i>0 </math> и ценность <math> c_i>0</math><math>, i= 1,2,...,n</math>.Есть рюкзак, определенной вместимости <math>P</math>. Задача — собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака. Обычно все параметры — целые, не отрицательные числа.
Рюкзак 0-1 (Шаблон:Lang-en)
Это самая распространенная разновидность рюкзака. Пусть <math> x_i </math> принимает два значения: <math> x_i= 1</math>, если груз упакован, и <math> x_i= 0</math> в противном случае, где <math> i= 1,2,...,n</math>. Задача:
максимизировать <math>\sum_{i=1}^n c_ix_i</math>
при наличии ограничения <math>\sum_{i=1}^n p_ix_i \le P</math> на вместимость рюкзакаШаблон:SfnШаблон:Sfn.
Ограниченный рюкзак (Шаблон:Lang-en)
Каждый предмет <math> x_i </math> может быть выбран ограниченное число раз. Задача:
максимизировать <math>\sum_{i=1}^n c_ix_i</math>
так, чтобы <math>\sum_{i=1}^n p_ix_i \le P</math> выполнялось условие на вместимость
и <math> x_i \in (0,1,...,m_i)</math> для всех <math> i= 1,2,...,n</math>Шаблон:Sfn.
Число <math>m_i</math> называют границейШаблон:Sfn.
Неограниченный рюкзак (целочисленный рюкзак) (Шаблон:Lang-en)
Каждый предмет <math> x_i </math> может быть выбран неограниченное число раз. Задача:
максимизировать <math>\sum_{i=1}^n c_ix_i</math>
так, чтобы <math>\sum_{i=1}^n p_ix_i \le P</math> выполнялось условие на вместимость
и целое <math> x_i \ge 0</math> для всех <math> i= 1,2,...,n</math>Шаблон:Sfn.
Рюкзак с мультивыбором (Шаблон:Lang-en)
Все предметы <math> x_i </math> разделяют на <math>s</math> классов <math>S_i</math>. Обязательным является условие выбора только одного предмета из каждого класса. <math>x_{i}</math> принимает значение только 0 и 1. Задача:
максимизировать <math>\sum_{i=1}^n \sum_{j\in S_i} c_{ij}x_{ij}</math>
так, чтобы <math>\sum_{i=1}^n \sum_{j\in S_i} p_{ij}x_{ij} \le P</math> выполнялось условие на вместимость,
<math>\sum_{j\in S_i}x_{ij}=1</math> для всех <math> i= 1,2,...,n</math>
Мультипликативный рюкзак (Шаблон:Lang-en)
Пусть у нас есть <math>n</math> предметов и <math>m</math> рюкзаков (<math>m\le n</math>). У каждого предмета, как и раньше, есть вес <math> p_j>0 </math> и ценность <math> c_j>0</math><math> j= 1,2,...,n</math>, у каждого рюкзака соответственно своя вместимость <math>P_i</math> при <math> i= 1,2,...,m</math>. <math>x_i \in {0,1}</math>. Задача:
максимизировать <math>\sum_{i=1}^m \sum_{j=1}^{n} c_{j}x_{ij}</math>
так, чтобы <math>\sum_{i=1}^n p_{j}x_{ij} \le P_i</math> выполнялось условие для всех <math> i= 1,2,...,m</math>,
<math>\sum_{j=1}^{m}x_{ij} \le 1</math> для всех <math> i= 1,2,...,n</math>Шаблон:Sfn.
Многомерный рюкзак (Шаблон:Lang-en)
Если есть более одного ограничения на рюкзак, например объем и вес, задачу называют m-мерной задачей о ранце. Например, для не ограниченного варианта:
максимизировать <math>\sum_{i=1}^n c_ix_i</math>
так, чтобы <math>\sum_{i=1}^n p_{ij}x_i \le P_j</math>, <math> j= 1,2,...,m</math>
и <math> x_i \ge 0</math> для всех <math> i= 1,2,...,n</math>Шаблон:Sfn.
Квадратичная задача о рюкзаке (Шаблон:Lang-en)
Квадратичная задача о ранце представляет собой модификацию классических задач о ранце с ценностью, являющейся квадратичной формой. Пусть <math>x = (x_1, .. ,x_n)</math> - вектор, задающий, сколько экземпляров каждого предмета окажется в рюкзаке. Задача:
максимизировать <math>x^TQx</math>
при условиях <math>\sum_{i=1}^n p_ix_i \le P</math>, <math>x \in B^n</math>, или
минимизировать <math>x^TQx</math>
при условиях <math>\sum_{i=1}^n p_ix_i \geq P</math>, <math>x \in B^n</math>.
При этом <math>Q</math> — неотрицательно определенная матрица размера <math>n \times n</math>, <math>B^n</math> задаёт ограничения на количество предметов[1].
Примечания
Литература
- на русском языке
- на английском языке
Ссылки
