Задача о рюкзаке (также задача о ранце) — NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в экономике, прикладной математике, криптографии и логистике.
В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.
Классическая постановка задачи Пусть имеется набор предметов, каждый из которых имеет два параметра — масса и ценность. Также имеется рюкзак определённой грузоподъёмности. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом ограничение рюкзака на суммарную массу.
Математически задача формулируется следующим образом: имеется грузов. Для каждого -го груза определены его масса и ценность , . Ограничение суммарного веса предметов в рюкзаке задаётся грузоподъёмностью . Необходимо максимизировать с ограничениями и .
Варианты задачи о рюкзаке
Постановка задачи допускает большое количество обобщений, в зависимости от условий, наложенных на рюкзак, предметы или их выбор. Наиболее популярными разновидностями являются следующие: Рюкзак 0-1 (): не более одного экземпляра каждого предмета. Ограниченный рюкзак (): не более заданного числа экземпляров каждого предмета. Неограниченный рюкзак (): произвольное количество экземпляров каждого предмета. Рюкзак с мультивыбором (): предметы разделены на группы, и из каждой группы требуется выбрать только один предмет. Множественный рюкзак (): есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить. Многомерный рюкзак (): вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна. Квадратичная задача о рюкзаке (): суммарная ценность задается неотрицательно определённой квадратичной формой.
Нелинейная задача о рюкзаке Одним из наиболее общих вариантов задачи о рюкзаке является нелинейный. Его можно сформулировать следующим образом:
Пусть вектор определяет количество экземпляров каждого предмета в рюкзаке. Тогда задача состоит в нахождении минимума функции
,
при заданном ограничении:
.
Функции предполагаются непрерывными и дифференцируемыми на . — целочисленная константа, множество непусто.
В случае линейных функций , задача сводится к одной из классических постановок, в зависимости от множества : — рюкзак 0-1 — неограниченный рюкзак — ограниченный рюкзак Свобода в выборе функций позволяет решать более широкий класс задач, включая , оптимальное распределение семплов в районированной выборке или решение квадратичной задачи о рюкзаке.
Точные методы решения Как было сказано выше, задача о рюкзаке относится к классу NP-полных, и для неё пока что не найден полиномиальный алгоритм, решающий её за разумное время. Поэтому при решении задачи о рюкзаке необходимо выбирать между точными алгоритмами, которые неприменимы для «больших» рюкзаков, и приближенными, которые работают быстро, но не гарантируют оптимального решения задачи.
Полный перебор Как и для других дискретных задач, задачу о рюкзаке можно решить, полностью перебрав все возможные решения.
По условию задачи имеется предметов, которые можно укладывать в рюкзак, и нужно определить максимальную стоимость груза, вес которого не превышает .
Для каждого предмета существует 2 варианта: предмет кладётся в рюкзак либо предмет не кладётся в рюкзак. Тогда перебор всех возможных вариантов имеет временну́ю сложность , что позволяет его использовать лишь для небольшого количества предметов. С ростом числа предметов задача становится неразрешимой данным методом за приемлемое время.
На рисунке показано дерево перебора для трёх предметов. Каждый лист соответствует некоторому подмножеству предметов. После составления дерева необходимо найти лист с максимальной ценностью среди тех, вес которых не превышает .
Метод ветвей и границ Метод ветвей и границ является вариацией метода полного перебора с той разницей, что исключаются заведомо неоптимальные ветви дерева полного перебора. Как и метод полного перебора, он позволяет найти оптимальное решение и поэтому относится к точным алгоритмам.
Оригинальный алгоритм, предложенный Питером Колесаром () в 1967 году, предлагает отсортировать предметы по их удельной стоимости (отношению ценности к весу) и строить дерево полного перебора. Его улучшение заключается в том, что в процессе построения дерева для каждого узла оценивается верхняя граница ценности решения, и продолжается построение дерева только для узла с максимальной оценкой. Когда максимальная верхняя граница оказывается в листе дерева, алгоритм заканчивает свою работу.
Способность метода ветвей и границ уменьшать количество вариантов перебора сильно опирается на входные данные. Его целесообразно применять, только если удельные ценности предметов значительно отличаются.
Методы динамического программирования
Задача о неограниченном рюкзаке При дополнительном ограничении на веса предметов, задачу о рюкзаке можно решить за псевдополиномиальное время методами динамического программирования.
Пусть вес каждого предмета является целым положительным числом. Тогда для решения задачи необходимо вычислить оптимальные решения для всех , где — заданная грузоподъемность. Определим как максимальную ценность предметов, которые можно поместить в рюкзак грузоподъемностью .
Для можно записать рекуррентные формулы:
, где — ценность и вес -го предмета соответственно, а максимум из пустого множества следует считать равным нулю.
Фактически последнее уравнение является функциональным уравнением Р. Беллмана или функциональным уравнением динамического программирования. В данном случае для его решения достаточно вычислить все значения , начиная с и до . Если дополнительно хранить на каждом шаге набор предметов, который реализует максимальную ценность, то алгоритм выдаст и оптимальный набор предметов.
Так как на каждом шаге необходимо найти максимум из предметов, алгоритм имеет вычислительную сложность . Поскольку может зависеть экспоненциально от размера входных данных, алгоритм является псевдополиномиальным. Поэтому эффективность данного алгоритма определяется значением . Алгоритм даёт отличные результаты при , но не очень хорошие для .
Задача о рюкзаке 0-1 Решение задачи о рюкзаке 0-1 близко к решению предыдущей задачи, но необходимо учесть тот факт, что каждый предмет имеется в единственном экземпляре. Пусть — максимальная ценность предметов, полученных из первых имеющихся предметов, с суммарным весом не превышающим .
Рекуррентные соотношения:
, если , если Вычисляя , можно найти точное решение. Если массив помещается в памяти машины, то данный алгоритм, вероятно, является одним из наиболее эффективных.// Ввод: // Ценности предметов (загруженные в массив v) // Веса предметов (загруженные в массив w) // Количество предметов (n) // Грузоподъемность (W)
for j from 0 to W do: m[0, j] := 0
for i from 1 to n do: for j from 0 to W do: if w[i] > j then: m[i, j] := m[i-1, j] else: m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
Проиллюстрировать решение методом динамического программирования можно следующим образом: на двумерной плоскости по оси откладывается количество предметов, по оси — их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось равны весу предмета. На втором шаге опять строятся 2 линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Положим длину горизонтальных дуг равной нулю, а наклонных — ценности предмета. Таким образом, любому решению задачи соответствует некоторый путь в построенном дереве. Задача сводится к нахождению пути максимальной длины. Пусть вместимость рюкзака . Номер предмета Ценность Вес 1 3 5 2 5 10 3 4 6 4 2 5 Из рисунка видно, что суммарная ценность для оптимального решения равна 7, так как это максимальная ценность в построенном дереве.
Динамическое программирование над ценностями предметов Рекуррентные соотношения можно записывать не только относительно веса предметов, но также и относительно ценности. Для этого обозначим за минимальный вес предметов суммарной ценностью , который можно получить из первых предметов. Если необходимый вес получить невозможно, то отметим это как .
После этого решим функциональное уравнение динамического программирования:
,
с начальными условиями:
Приближенные методы решения Как и для большинства NP-полных задач, не всегда необходимо получать точное решение, так как решения, близкие к оптимальным, могут применяться в прикладных задачах.
Жадный алгоритм Для решения задачи жадным алгоритмом необходимо отсортировать вещи по их удельной ценности (то есть отношению ценности предмета к его весу), и поместить в рюкзак предметы с наибольшей удельной ценностью.
Время работы данного алгоритма складывается из времени сортировки и времени укладки. Сложность сортировки предметов составляет . Далее происходит вычисление того, сколько предметов поместится в рюкзак за общее время . Итоговая сложность при необходимости сортировки и при уже отсортированных данных.
Пример. Пусть вместимость рюкзака . Предметы уже отсортированы по удельной ценности. Применим жадный алгоритм. i вес цена цена/вес 1 15 60 <center> 4 2 30 90 <center> 3 3 50 100 <center> 2
Кладём в рюкзак первый предмет, а за ним второй. Третий предмет в рюкзак не влезет. Суммарная ценность вещей в рюкзаке равна 150. Если бы были взяты второй и третий предметы, то суммарная ценность составила бы 190. Таким образом, мы получили некоторое неоптимальное решение.
Следует понимать, что жадный алгоритм может привести к ответу, сколь угодно далёкому от оптимального. Например, если один предмет имеет вес 1 и стоимость 2, а другой — вес W и стоимость W, то жадный алгоритм наберёт итоговую стоимость 2 при оптимальном ответе W. При этом тот же алгоритм для неограниченной задачи о рюкзаке приведёт к ответу, составляющему не менее 50 % от ценности оптимального.
Впервые жадный алгоритм был предложен Джорджем Данцигом для решения задачи о неограниченном рюкзаке.
Приближенная схема полностью полиномиального времени Так как точного алгоритма решения задачи за полиномиальное время не было найдено, появилась задача получить полиномиальное решение с гарантированной точностью . Для этого существует целый ряд приближённых схем полностью полиномиального времени, то есть со сложностью, являющейся полиномом от и .
Идея, стоящая за классической схемой, заключается в снижении точности, с которой заданы ценности предметов. Объединяя предметы близкой ценности в одну группу, можно снизить количество разных предметов. Алгоритм записывается следующим образом: Найдём приближённое решение при помощи жадного алгоритма. Пусть — точное решение. Тогда из оценки эффективности жадного алгоритма . Отмасштабируем ценности следующим образом: . Алгоритмом динамического программирования для задачи с целочисленными ценностями предметов находим решение. Существует множество различных схем аппроксимации. Тем не менее, они сильно зависят от формулировки задачи о рюкзаке. Например, если в условии появляется второе ограничение типа неравенства (двухмерный рюкзак), то задача уже не имеет известной схемы полиномиального времени.
Генетические алгоритмы