Задача о рюкзаке — различия между версиями
| Строка 54: | Строка 54: | ||
Входными данными являются: ''' n; b; {a<sub>1</sub>,a<sub>2</sub>,...,a<sub>n</sub>}; {c<sub>1</sub>,c<sub>2</sub>,...,c<sub>n</sub>}; {m<sub>1</sub>,m<sub>2</sub>,...,m<sub>n</sub>}'''. | Входными данными являются: ''' n; b; {a<sub>1</sub>,a<sub>2</sub>,...,a<sub>n</sub>}; {c<sub>1</sub>,c<sub>2</sub>,...,c<sub>n</sub>}; {m<sub>1</sub>,m<sub>2</sub>,...,m<sub>n</sub>}'''. | ||
== Другие задачи: == | == Другие задачи: == | ||
| − | + | {{Список ЗМП}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Ссылки == | == Ссылки == | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Целочисленное программирование]][[Категория:Логистика]][[Категория:Алгоритмы]] | [[Категория:Целочисленное программирование]][[Категория:Логистика]][[Категория:Алгоритмы]] | ||
Текущая версия на 12:51, 29 сентября 2016
Задача о рюкзаке — это задача целочисленного программирования о загрузке заданного объёма (веса) предметами наибольшей стоимости (полезности).
Содержание
Постановка задачи
Имеется 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}.
