Задача о рюкзаке — различия между версиями
BenderBot (обсуждение | вклад) м (реплицировано из внутренней CustisWiki) |
StasFomin (обсуждение | вклад) м |
||
Строка 1: | Строка 1: | ||
− | Задача о рюкзаке (Knapsack problem) содержательно | + | Задача о рюкзаке ([[Knapsack problem]]) содержательно |
означает выбор предметов с наибольшей суммарной | означает выбор предметов с наибольшей суммарной | ||
стоимостью, умещающихся в рюкзак заданного размера. | стоимостью, умещающихся в рюкзак заданного размера. |
Версия 19:23, 19 апреля 2006
Задача о рюкзаке (Knapsack problem) содержательно означает выбор предметов с наибольшей суммарной стоимостью, умещающихся в рюкзак заданного размера. Эта задача часто возникает при выборе оптимального управления в различных экономико-финансовых областях (распределение бюджета отдела по проектам и т. п.).
Задача имеет несколько более формальных постановок, представленных ниже.
0-1 Рюкзак
Даны натуральные числа (называемые «размерами» или «весами» предметов), («стоимости» предметов) и B («размер» рюкзака).
Найти максимальное значение целевой функции
с ограничением на размер «рюкзака»
Алгоритмы
- Задача о рюкзаке:жадный алгоритм
- Задача о рюкзаке:динамическое программирование
- Задача о рюкзаке:PTAS
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
Репликация: База Знаний «Заказных Информ Систем» → «Задача о рюкзаке»