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

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

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

Содержание

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

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

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

[math]L(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max[/math]
[math]\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}[/math]

или

[math]L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max[/math]
[math]\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}[/math]

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

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

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

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

ЗР11.JPG

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

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

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

[math]L(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max[/math]
[math]\begin{cases}\sum\limits_{j=1}^n a_jx_j \le b, \\ x_j \in \{0;1\}, \ \forall j\in N_n\end{cases}[/math]

или

[math]L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max[/math]
[math]\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}[/math]

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

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

ЗР23.JPG

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

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

[math]L(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max[/math]
[math]\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}[/math]

или

[math]L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max[/math]
[math]\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}[/math]

где 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}.

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

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

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты