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