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

Материал из свободной русской энциклопедии «Традиция»
(перенаправлено с «Knapsack problem»)
Перейти к: навигация, поиск

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

Задача имеет несколько более формальных постановок, представленных ниже.

0-1 Рюкзак[править]

Даны натуральные числа \(a_1,\ldots,a_n\) (называемые «размерами» или «весами» предметов), \(c_1, \ldots, c_n\) («стоимости» предметов) и B («размер» рюкзака).

Найти максимальное значение \(f^*\) целевой функции \( f \equiv \sum_{i=1}^n c_i x_i \to \max \)

с ограничением на размер «рюкзака» \( \sum_{i=1}^n a_i x_i \leq B, \ \ \ x_i \in \{0,1\}.\)


Алгоритмы[править]


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.