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

Математическая модель ЗР

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

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

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

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

или

,

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

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

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

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

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

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

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

или

,

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

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

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

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

или

,

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