Персональные инструменты
 

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

Материал из CustisWiki

Версия от 19:48, 23 октября 2008; WikiSysop (обсуждение | вклад) (1 версия)

Это снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений.
Перейти к: навигация, поиск

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

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

0-1 Рюкзак

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

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

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


Алгоритмы


Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.