Задача о рюкзаке — различия между версиями
(начало) |
|||
Строка 57: | Строка 57: | ||
== Ссылки == | == Ссылки == | ||
*[[Участник:Logic-samara]] | *[[Участник:Logic-samara]] | ||
− | [[Категория:Целочисленное программирование]][[Категория:Логистика]][[Категория:Алгоритмы]] | + | [[Категория:Математика]][[Категория:Целочисленное программирование]][[Категория:Логистика]][[Категория:Алгоритмы]] |
Текущая версия на 04:43, 10 апреля 2023
Задача о рюкзаке — это задача целочисленного программирования о загрузке заданного объёма (веса) предметами наибольшей стоимости (полезности).
Содержание
Постановка задачи
Имеется n видов предметов (грузов) и рюкзак ёмкостью (грузовместимостью, грузоподъёмностью) b. Пусть заданы объём (вес) aj и стоимость (полезность) cj для j-ого предмета, j=1,2,…,n. Необходимо определить вариант загрузки с максимальной стоимостью.
Задача о рюкзаке (ЗР) формулируется следующим образом:
или
где xj — количество предметов j-го вида, j=1,2,…,n.
Задача о рюкзаке относится к целочисленному программированию. Для решения задачи о рюкзаке применяется метод динамического программирования.
Алгоритм решения
Входные данные: n; b; {a1,a2,...,an}; {c1,c2,...,cn}.
Выходные данные: L; {x1,x2,...,xn}.
Задача о рюкзаке без повторений
При дополнительном ограничении - запрете повторений предметов - получаем задачу о рюкзаке без повторений, которая формулируется следующим образом:
или
где xj — означает выбор предмета j-го вида, j=1,2,…,n.
При этом алгоритм решения модифицируется в части строки 7, она меняется на строку вида:
Задача о рюкзаке с ограниченным числом повторений
При дополнительном ограничении на число повторений предметов получаем задачу о рюкзаке с ограниченным числом повторений, которая формулируется следующим образом:
или
где xj — количество предметов j-го вида, j=1,2,…,n;
mj — число возможных повторений предметов j-го вида, j=1,2,…,n.
При этом алгоритм решения модифицируется в части строки 7, она меняется на строку вида:
Входными данными являются: n; b; {a1,a2,...,an}; {c1,c2,...,cn}; {m1,m2,...,mn}.