Задача о ранце

Материал из Википедии — свободной энциклопедии

Задача о ранце (рюкзаке) — одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные задачи часто возникают в экономике, прикладной математике, криптографии. В общем виде, задачу можно сформулировать так: из неограниченного множества предметов, каждый из которых имеет свою стоимость и ценность, требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную ценность при одновременном соблюдении ограничения на суммарную стоимость.

Задача о ранце в случае, когда вес каждого предмета представляет собой целое число, может быть решена с помощью динамического программирования.

[править] См. также

• Задача об упаковке в контейнеры

[править] Литература

• Ананий В. Левитин Глава 3. Метод грубой силы: Задача о рюкзаке // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 160-163. — ISBN 0-201-74395-7