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

Задача о рюкзаке — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (реплицировано из внутренней CustisWiki)
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
Задача о рюкзаке ([[Knapsack problem]]) содержательно  
+
Задача о рюкзаке (Knapsack problem) содержательно  
 
означает выбор предметов с наибольшей суммарной
 
означает выбор предметов с наибольшей суммарной
 
стоимостью, умещающихся в рюкзак заданного размера.
 
стоимостью, умещающихся в рюкзак заданного размера.

Версия 13:47, 19 апреля 2006

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

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

0-1 Рюкзак

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

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

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


Алгоритмы


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

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