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