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

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

Информатика. Алгоритм "укладки рюкзака" // Центр онлайн-обучения «Фоксфорд» [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$

${\begin{cases}\sum \limits _{j=1}^{n}a_{j}x_{j}\leq b,\\0\leq 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}.

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

• Каноническая задача;
• Производственная задача;
• Общая прямая задача линейного программирования;
• Общая двойственная задача линейного программирования;
• Классическая транспортная задача;
• Распределительная задача;
• Задача о назначениях;
• Транспортная задача с промежуточными пунктами;
• Трёхиндексная транспортная задача;
• Задача целочисленного программирования.

Ссылки

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