Задача о рюкзаке — различия между версиями
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
|||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
[[файл:ЗР01.JPG|thumb|300|[[Математическая модель]] ЗР]] | [[файл:ЗР01.JPG|thumb|300|[[Математическая модель]] ЗР]] | ||
| − | |||
'''Задача о рюкзаке''' — это [[задача целочисленного программирования]] о загрузке заданного объёма (веса) предметами наибольшей стоимости (полезности). | '''Задача о рюкзаке''' — это [[задача целочисленного программирования]] о загрузке заданного объёма (веса) предметами наибольшей стоимости (полезности). | ||
| − | |||
== Постановка задачи == | == Постановка задачи == | ||
Имеется '''n''' видов предметов (грузов) и рюкзак ёмкостью (грузовместимостью, грузоподъёмностью) '''b'''. Пусть заданы объём (вес) '''a<sub>j</sub>''' и стоимость (полезность) '''c<sub>j</sub>''' для '''j'''-ого предмета, '''j=1,2,…,n'''. Необходимо определить вариант загрузки с максимальной стоимостью. | Имеется '''n''' видов предметов (грузов) и рюкзак ёмкостью (грузовместимостью, грузоподъёмностью) '''b'''. Пусть заданы объём (вес) '''a<sub>j</sub>''' и стоимость (полезность) '''c<sub>j</sub>''' для '''j'''-ого предмета, '''j=1,2,…,n'''. Необходимо определить вариант загрузки с максимальной стоимостью. | ||
| Строка 17: | Строка 15: | ||
Задача о рюкзаке относится к целочисленному программированию. Для решения задачи о рюкзаке применяется метод динамического программирования. | Задача о рюкзаке относится к целочисленному программированию. Для решения задачи о рюкзаке применяется метод динамического программирования. | ||
| − | |||
== Алгоритм решения == | == Алгоритм решения == | ||
Входные данные: ''' 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>}'''. | Входные данные: ''' 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>}'''. | ||
| Строка 24: | Строка 21: | ||
Выходные данные: '''L; {x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n</sub>}'''. | Выходные данные: '''L; {x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n</sub>}'''. | ||
| − | |||
== Задача о рюкзаке без повторений == | == Задача о рюкзаке без повторений == | ||
При дополнительном ограничении - запрете повторений предметов - получаем задачу о рюкзаке без повторений, которая формулируется следующим образом: | При дополнительном ограничении - запрете повторений предметов - получаем задачу о рюкзаке без повторений, которая формулируется следующим образом: | ||
| Строка 39: | Строка 35: | ||
[[файл:ЗР23.JPG]] | [[файл:ЗР23.JPG]] | ||
| − | |||
== Задача о рюкзаке с ограниченным числом повторений == | == Задача о рюкзаке с ограниченным числом повторений == | ||
При дополнительном ограничении на число повторений предметов получаем задачу о рюкзаке с ограниченным числом повторений, которая формулируется следующим образом: | При дополнительном ограничении на число повторений предметов получаем задачу о рюкзаке с ограниченным числом повторений, которая формулируется следующим образом: | ||
| Строка 58: | Строка 53: | ||
Входными данными являются: ''' 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}.
