Задача о ранце

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