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

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

Материал из CustisWiki

Версия от 22:07, 20 апреля 2006; BenderBot (обсуждение | вклад) (реплицировано из внутренней CustisWiki)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

0-1 Рюкзак

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

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

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


Алгоритмы


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

Репликация: База Знаний «Заказных Информ Систем» → «Задача о рюкзаке»