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

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

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

0-1 Рюкзак

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

Найти максимальное значение целевой функции

с ограничением на размер «рюкзака»

Алгоритмы

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

---

Внимание! Эта статья была создана путем автоматического реплицирования из внутренней базы знаний компании Заказные Информ Системы. Любые правки этой статьи могут быть перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».