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

Задача о рюкзаке (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\}.$

Алгоритмы

• Задача о рюкзаке:жадный алгоритм
• Задача о рюкзаке:динамическое программирование
• Задача о рюкзаке:PTAS

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