Описание Области
подробнее…
Постановка задачи
Задача о ранце (или задача о рюкзаке) – одна из NP-полных задач комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о ранце можно столкнуться в экономике, прикладной математике, криптографии и логистике.
В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.
Дано:
• Ранец заданной вместимости.
• Набор вещей, которые можно положить в ранец. Каждая вещь имеет две характеристики: масса (объем) и стоимость (ценность).
Требуется:
Выбрать из этих вещей такой набор, чтобы суммарный вес не превосходил заданной вместимости ранца, а суммарная ценность (стоимость) была максимальна.
кратко