Задача о рюкзаке

---

Задача о рюкзаке (также задача о ранце) — NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в экономике, прикладной математике, криптографии и логистике.

В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.

Пусть имеется набор предметов, каждый из которых имеет два параметра — масса и ценность. Также имеется рюкзак определённой грузоподъёмности. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом ограничение рюкзака на суммарную массу.

Математически задача формулируется следующим образом: имеется ${\displaystyle n}$ грузов. Для каждого ${\displaystyle i}$-го груза определены его масса ${\displaystyle w_{i}>0}$ и ценность ${\displaystyle v_{i}>0}$, ${\displaystyle i=1,2,...,n}$. Ограничение суммарного веса предметов в рюкзаке задаётся грузоподъёмностью ${\displaystyle W}$. Необходимо

Постановка задачи допускает большое количество обобщений, в зависимости от условий, наложенных на рюкзак, предметы или их выбор. Наиболее популярными разновидностями являются следующие:

Одним из наиболее общих вариантов задачи о рюкзаке является нелинейный. Его можно сформулировать следующим образом:

---