Имеется n видов предметов (грузов) и рюкзак ёмкостью (грузовместимостью, грузоподъёмностью) b. Пусть заданы объём (вес) aj и стоимость (полезность) cj для j-ого предмета, j=1,2,…,n. Необходимо определить вариант загрузки с максимальной стоимостью.
Задача о рюкзаке (ЗР) формулируется следующим образом:
или
где xj — количество предметов j-го вида, j=1,2,…,n.
Задача о рюкзаке относится к целочисленному программированию. Для решения задачи о рюкзаке применяется метод динамического программирования.
При дополнительном ограничении — запрете повторений предметов — получаем задачу о рюкзаке без повторений, которая формулируется следующим образом:
или
где xj — означает выбор предмета j-го вида, j=1,2,…,n.
При этом алгоритм решения модифицируется в части строки 7, она меняется на строку вида:
Задача о рюкзаке с ограниченным числом повторений[править]
При дополнительном ограничении на число повторений предметов получаем задачу о рюкзаке с ограниченным числом повторений, которая формулируется следующим образом:
или
где xj — количество предметов j-го вида, j=1,2,…,n;
mj — число возможных повторений предметов j-го вида, j=1,2,…,n.
При этом алгоритм решения модифицируется в части строки 7, она меняется на строку вида: