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

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

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

Постановка задачи[править]

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = \sum\limits_{j=1}^n c_jx_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, \\ x_j \in \mathbb{N} \cup 0, \forall j\in N_n\end{cases}}
или
Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max}
Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}a_1x_1+a_2x_2+\ldots+a_nx_n \le b \\ x_1 \ge 0, \ x_2 \ge 0, \ldots, \ x_n \ge 0 \\ x_1 \in \mathbb{Z}, \ x_2 \in \mathbb{Z}, \ldots, \ x_n \in \mathbb{Z} \end{cases}}

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

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

Алгоритм решения[править]

Входные данные: n; b; {a1,a2,...,an}; {c1,c2,...,cn}.

ЗР11.JPG

Выходные данные: L; {x1,x2,...,xn}.

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X)=\sum\limits_{j=1}^n c_jx_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, \\ x_j\in \{0;1\}, \forall j\in N_n\end{cases}}
или
Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max}
Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}a_1x_1+a_2x_2+\ldots+a_nx_n \le b \\ x_1 \in \{0;1\}, \ x_2 \in \{0;1\}, \ldots, \ x_n \in \{0;1\} \end{cases}}

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

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

ЗР23.JPG

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = \sum\limits_{j=1}^n c_jx_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}}

или

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max}
Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}a_1x_1+a_2x_2+\ldots+a_nx_n \le b \\ 0 \le x_j \in m_j, \ \forall x_j \in \mathbb{Z}, \ \forall j\in N_n \end{cases}}

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

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

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

ЗР33.JPG

Входными данными являются: n; b; {a1,a2,...,an}; {c1,c2,...,cn}; {m1,m2,...,mn}.

Другие задачи:[править]


Ссылки[править]