Задача о рюкзаке
Задача о рюкзаке (Knapsack problem) содержательно означает выбор предметов с наибольшей суммарной стоимостью, умещающихся в рюкзак заданного размера. Эта задача часто возникает при выборе оптимального управления в различных экономико-финансовых областях (распределение бюджета отдела по проектам и т. п.).
Задача имеет несколько более формальных постановок, представленных ниже.
0-1 Рюкзак
Даны натуральные числа (называемые «размерами» или «весами» предметов), («стоимости» предметов) и B («размер» рюкзака).
Найти максимальное значение целевой функции
с ограничением на размер «рюкзака»
Алгоритмы
- Задача о рюкзаке:жадный алгоритм
- Задача о рюкзаке:динамическое программирование
- Задача о рюкзаке:PTAS
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
Репликация: База Знаний «Заказных Информ Систем» → «Задача о рюкзаке»