Задача о рюкзаке — различия между версиями
Материал из DISCOPAL
м (1 версия) |
(нет различий)
|
Текущая версия на 16:48, 23 октября 2008
Задача о рюкзаке (Knapsack problem) содержательно означает выбор предметов с наибольшей суммарной стоимостью, умещающихся в рюкзак заданного размера. Эта задача часто возникает при выборе оптимального управления в различных экономико-финансовых областях (распределение бюджета отдела по проектам и т. п.).
Задача имеет несколько более формальных постановок, представленных ниже.
0-1 Рюкзак
Даны натуральные числа (называемые «размерами» или «весами» предметов), («стоимости» предметов) и B («размер» рюкзака).
Найти максимальное значение целевой функции
с ограничением на размер «рюкзака»