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

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

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

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

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

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

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

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


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


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