Задача о рюкзаке

Математическая модель задачи о рюкзаке

Информатика. Алгоритм "укладки рюкзака" // Центр онлайн-обучения «Фоксфорд» [11:46]

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

Постановка задачи

Имеется n видов предметов (грузов) и рюкзак ёмкостью (грузовместимостью, грузоподъёмностью) b. Пусть заданы объём (вес) a_j и стоимость (полезность) c_j для j-ого предмета, j=1,2,…,n. Необходимо определить вариант загрузки с максимальной стоимостью.

Задача о рюкзаке (ЗР) формулируется следующим образом:

$L(X)=\sum \limits _{j=1}^{n}c_{j}x_{j}\rightarrow \max$

${\begin{cases}\sum \limits _{j=1}^{n}a_{j}x_{j}\leq b,\\x_{j}\in \mathbb {N} \cup 0,\forall j\in N_{n}\end{cases}}$

или

$L(X)=c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}\rightarrow \max$

${\begin{cases}a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\leq b\\x_{1}\geq 0,\ x_{2}\geq 0,\ldots ,\ x_{n}\geq 0\\x_{1}\in \mathbb {Z} ,\ x_{2}\in \mathbb {Z} ,\ldots ,\ x_{n}\in \mathbb {Z} \end{cases}}$

где x_j — количество предметов j-го вида, j=1,2,…,n.

Задача о рюкзаке относится к целочисленному программированию. Для решения задачи о рюкзаке применяется метод динамического программирования.

Алгоритм решения

Входные данные: n; b; {a₁,a₂,...,a_n}; {c₁,c₂,...,c_n}.

Выходные данные: L; {x₁,x₂,...,x_n}.

Задача о рюкзаке без повторений

При дополнительном ограничении — запрете повторений предметов — получаем задачу о рюкзаке без повторений, которая формулируется следующим образом:

$L(X)=\sum \limits _{j=1}^{n}c_{j}x_{j}\rightarrow \max$

${\begin{cases}\sum \limits _{j=1}^{n}a_{j}x_{j}\leq b,\\x_{j}\in \{0;1\},\forall j\in N_{n}\end{cases}}$

или

$L(X)=c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}\rightarrow \max$

${\begin{cases}a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\leq b\\x_{1}\in \{0;1\},\ x_{2}\in \{0;1\},\ldots ,\ x_{n}\in \{0;1\}\end{cases}}$

где x_j — означает выбор предмета j-го вида, j=1,2,…,n.

При этом алгоритм решения модифицируется в части строки 7, она меняется на строку вида:

Задача о рюкзаке с ограниченным числом повторений

При дополнительном ограничении на число повторений предметов получаем задачу о рюкзаке с ограниченным числом повторений, которая формулируется следующим образом:

$L(X)=\sum \limits _{j=1}^{n}c_{j}x_{j}\rightarrow \max$

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}\sum\limits_{j=1}^n a_jx_j \le b, \\ 0 \le x_j \in m_j, \ \forall x_j \in \mathbb{Z}, \ \forall j\in N_n\end{cases}}

или

$L(X)=c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}\rightarrow \max$

${\begin{cases}a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\leq b\\0\leq x_{j}\in m_{j},\ \forall x_{j}\in \mathbb {Z} ,\ \forall j\in N_{n}\end{cases}}$

где x_j — количество предметов j-го вида, j=1,2,…,n;

m_j — число возможных повторений предметов j-го вида, j=1,2,…,n.

При этом алгоритм решения модифицируется в части строки 7, она меняется на строку вида:

Входными данными являются: n; b; {a₁,a₂,...,a_n}; {c₁,c₂,...,c_n}; {m₁,m₂,...,m_n}.

Другие задачи:

1. Каноническая задача;
2. Производственная задача;
3. Общая прямая задача линейного программирования;
4. Общая двойственная задача линейного программирования;
5. Задачи транспортного типа;
6. Задача целочисленного программирования;
7. Задача о рюкзаке;
8. Задача распределения средств;
9. Задача замены оборудования.

Ссылки

• Участник:Logic-samara