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

Материал из ALL
Перейти к: навигация, поиск

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

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

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

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

ЗР01.JPG

или

ЗР02.JPG,

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

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

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

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

ЗР11.JPG

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

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

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

ЗР21.JPG

или

ЗР22.JPG,

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

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

ЗР23.JPG

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

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

ЗР31.JPG

или

ЗР32.JPG,

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

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

Ссылки