Задача о рюкзаке

Постановка задачи допускает большое количество обобщений, в зависимости от условий, наложенных на рюкзак, предметы или их выбор. Наиболее популярными разновидностями являются следующие:

1. Рюкзак 0-1 (англ. 0-1 Knapsack Problem)[2]: не более одного экземпляра каждого предмета.
2. Ограниченный рюкзак (англ. Bounded Knapsack Problem)[3]: не более заданного числа экземпляров каждого предмета.
3. Неограниченный рюкзак (англ. Unbounded Knapsack Problem)[3]: произвольное количество экземпляров каждого предмета.
4. Рюкзак с мультивыбором (англ. Multiple-choice Knapsack Problem)[4]: предметы разделены на группы, и из каждой группы требуется выбрать только один предмет.
5. Множественный рюкзак (англ. Multiple Knapsack Problem)[5]: есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить.
6. Многомерный рюкзак (англ. Multi-dimensional knapsack problem): вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна[4].
7. Квадратичная задача о рюкзаке (англ. Quadratic knapsack problem): суммарная ценность задается неотрицательно определённой квадратичной формой[6].

Как и для других дискретных задач, задачу о рюкзаке можно решить, полностью перебрав все возможные решения.

По условию задачи имеется ${\displaystyle N}$ предметов, которые можно укладывать в рюкзак, и нужно определить максимальную стоимость груза, вес которого не превышает ${\displaystyle W}$.

Для каждого предмета существует 2 варианта: предмет кладётся в рюкзак, либо предмет не кладётся в рюкзак. Тогда перебор всех возможных вариантов имеет временну́ю сложность ${\displaystyle O(2^{N})}$, что позволяет его использовать лишь для небольшого количества предметов[8]. С ростом числа предметов задача становится неразрешимой данным методом за приемлемое время.

На рисунке показано дерево перебора для трёх предметов. Каждый лист соответствует некоторому подмножеству предметов. После составления дерева необходимо найти лист с максимальной ценностью среди тех, вес которых не превышает ${\displaystyle W}$[9].

Метод ветвей и границ является вариацией метода полного перебора с той разницей, что исключаются заведомо неоптимальные ветви дерева полного перебора. Как и метод полного перебора, он позволяет найти оптимальное решение и поэтому относится к точным алгоритмам.

Оригинальный алгоритм, предложенный Питером Колесаром (англ. Peter Kolesar) в 1967 году, предлагает отсортировать предметы по их удельной стоимости (отношению ценности к весу) и строить дерево полного перебора. Его улучшение заключается в том, что в процессе построения дерева для каждого узла оценивается верхняя граница ценности решения, и продолжается построение дерева только для узла с максимальной оценкой[10]. Когда максимальная верхняя граница оказывается в листе дерева, алгоритм заканчивает свою работу.

Способность метода ветвей и границ уменьшать количество вариантов перебора сильно опирается на входные данные. Его целесообразно применять только если удельные ценности предметов значительно отличаются[11].

При дополнительном ограничении на веса предметов, задачу о рюкзаке можно решить за псевдополиномиальное время методами динамического программирования.

Пусть вес каждого предмета ${\displaystyle w_{i}}$ является целым положительным числом. Тогда для решения задачи необходимо вычислить оптимальные решения для всех ${\displaystyle w\in \mathbb {Z} :0\leq w\leq W}$, где ${\displaystyle W}$ — заданная грузоподъемность. Определим ${\displaystyle m[w]}$ как максимальную ценность предметов, которые можно поместить в рюкзак грузоподъемностью ${\displaystyle w}$.

Для ${\displaystyle m[w]}$ можно записать рекуррентные формулы:

• ${\displaystyle m[0]=0}$
• ${\displaystyle m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])}$[12],

где ${\displaystyle v_{i},w_{i}}$ — ценность и вес ${\displaystyle i}$-го предмета соответственно, а максимум из пустого множества следует считать равным нулю.

Фактически последнее уравнение является функциональным уравнением Р. Беллмана или функциональным уравнением динамического программирования. В данном случае для его решения достаточно вычислить все значения ${\displaystyle m[w]}$, начиная с ${\displaystyle 0}$ и до ${\displaystyle W}$[12]. Если дополнительно хранить на каждом шаге набор предметов, который реализует максимальную ценность, то алгоритм выдаст и оптимальный набор предметов.

Так как на каждом шаге необходимо найти максимум из ${\displaystyle n}$ предметов, алгоритм имеет вычислительную сложность ${\displaystyle O(nW)}$. Поскольку ${\displaystyle W}$ может зависеть экспоненциально от размера входных данных, алгоритм является псевдополиномиальным. Поэтому эффективность данного алгоритма определяется значением ${\displaystyle W}$. Алгоритм даёт отличные результаты при ${\displaystyle W\leq 1000}$, но не очень хорошие для ${\displaystyle W\geq 10\ 000\ 000}$[13].

Решение задачи о рюкзаке 0-1 близко к решению предыдущей задачи, но необходимо учесть тот факт, что каждый предмет имеется в единственном экземпляре. Пусть ${\displaystyle m[i,w]}$ — максимальная ценность предметов, полученных из первых ${\displaystyle i}$ имеющихся предметов, с суммарным весом не превышающим ${\displaystyle w}$.

Рекуррентные соотношения:

• ${\displaystyle m[0,w]=0}$
• ${\displaystyle m[i,\,w]=m[i-1,\,w]}$, если ${\displaystyle w_{i}>w}$
• ${\displaystyle m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})}$, если ${\displaystyle w_{i}\leq w}$

Вычисляя ${\displaystyle m[n,W]}$, можно найти точное решение. Если массив ${\displaystyle m[i,w]}$ помещается в памяти машины, то данный алгоритм, вероятно, является одним из наиболее эффективных[12].

// Ввод:
// Ценности предметов (загруженные в массив 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])

Сеть, иллюстрирующая наполнение рюкзака. В квадратных скобках указаны суммарная ценность на данном шаге алгоритма, оптимальное решение помечено кругом

Проиллюстрировать решение методом динамического программирования можно следующим образом: на двумерной плоскости по оси ${\displaystyle X}$ откладывается количество предметов, по оси ${\displaystyle Y}$ — их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось ${\displaystyle Y}$ равны весу предмета. На втором шаге опять строятся 2 линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Положим длину горизонтальных дуг равной нулю, а наклонных — ценности предмета[14]. Таким образом, любому решению задачи соответствует некоторый путь в построенном дереве. Задача сводится к нахождению пути максимальной длины[14]. Пусть вместимость рюкзака ${\displaystyle W=14}$.

Из рисунка видно, что суммарная ценность для оптимального решения равна 7, так как это максимальная ценность в построенном дереве.

Рекуррентные соотношения можно записывать не только относительно веса предметов, но также и относительно ценности. Для этого обозначим за ${\displaystyle y[i,V]}$ минимальный вес предметов суммарной ценностью ${\displaystyle V}$, который можно получить из первых ${\displaystyle i}$ предметов. Если необходимый вес получить невозможно, то отметим это как ${\displaystyle y[i,V]=W+1}$.

После этого решим функциональное уравнение динамического программирования:

${\displaystyle y[i,V]={\begin{cases}y[i-1,V],&{\text{if }}V<v_{i}\\\min\{\ y[i-1,V],y[i-1,V-v_{i}]+w_{i}\},&{\text{if }}V\geq v_{i}\end{cases}}}$,

с начальными условиями:

${\displaystyle y[0,0]=0}$

${\displaystyle y[0,V]=W+1}$[15]

Для решения задачи жадным алгоритмом, необходимо отсортировать вещи по их удельной ценности (то есть отношению ценности предмета к его весу), и поместить в рюкзак предметы с наибольшей удельной ценностью[10].

Время работы данного алгоритма складывается из времени сортировки и времени укладки. Сложность сортировки предметов составляет ${\displaystyle O(N\log(N))}$. Далее происходит вычисление того, сколько предметов поместится в рюкзак за общее время ${\displaystyle O(N)}$[10]. Итоговая сложность ${\displaystyle O(N\log(N))}$ при необходимости сортировки и ${\displaystyle O(N)}$ при уже отсортированных данных[10].

Пример. Пусть вместимость рюкзака ${\displaystyle W=80}$. Предметы уже отсортированы по удельной ценности. Применим жадный алгоритм.

Кладём в рюкзак первый предмет, а за ним второй. Третий предмет в рюкзак не влезет. Суммарная ценность вещей в рюкзаке равна 150. Если бы были взяты второй и третий предметы, то суммарная ценность составила бы 190. Таким образом, мы получили некоторое неоптимальное решение.

Следует понимать, что жадный алгоритм может привести к ответу сколь угодно далёкому от оптимального. Например, если один предмет имеет вес 1 и стоимость 2, а другой — вес W и стоимость W, то жадный алгоритм наберёт итоговую стоимость 2 при оптимальном ответе W. При этом тот же алгоритм для неограниченной задачи о рюкзаке приведёт к ответу, составляющему не менее 50 % от ценности оптимального[10]. (В приведённом примере жадный алгоритм возьмёт 5 первых предметов с общей ценностью 300, и это совпадает с оптимальным решением.)

Впервые жадный алгоритм был предложен Джорджем Данцигом[16] для решения задачи о неограниченном рюкзаке.

Так как точного алгоритма решения задачи за полиномиальное время не было найдено, появилась задача получить полиномиальное решение с гарантированной точностью ${\displaystyle 1-\varepsilon }$. Для этого существует целый ряд приближённых схем полностью полиномиального времени, то есть со сложностью, являющейся полиномом от ${\displaystyle n}$ и ${\displaystyle {\frac {1}{\varepsilon }}}$.

Идея, стоящая за классической схемой, заключается в снижении точности, с которой заданы ценности предметов. Объединяя предметы близкой ценности в одну группу, можно снизить количество разных предметов. Алгоритм записывается следующим образом[15]:

1. Найдём приближённое решение ${\displaystyle x^{l}}$ при помощи жадного алгоритма. Пусть ${\displaystyle x^{*}}$ — точное решение. Тогда из оценки эффективности жадного алгоритма ${\displaystyle x^{l}\leq x^{*}\leq 2x^{l}}$.
2. Отмасштабируем ценности следующим образом: ${\displaystyle v'_{i}=\left\lfloor {\frac {v_{i}}{\frac {x^{l}\varepsilon }{n}}}\right\rfloor }$.
3. Алгоритмом динамического программирования для задачи с целочисленными ценностями предметов находим решение.

Существует множество различных схем аппроксимации. Тем не менее, они сильно зависят от формулировки задачи о рюкзаке. Например, если в условии появляется второе ограничение типа неравенства (двухмерный рюкзак), то задача уже не имеет известной схемы полиномиального времени[17].

Пример эволюции популяции при использовании генетического алгоритма. Объектами являются строчки, кодирующие в бинарном виде какие объекты кладутся в рюкзак. Например, строчка (0,1,0,1,0) соответствует выбору коробок весами 12 кг и 7 кг .

Как и для других NP-трудных задач оптимизации, для решения задачи о рюкзаке применяются генетические алгоритмы. Они не гарантируют нахождения оптимального решения за полиномиальное время и не дают оценку близости решения к оптимальному, но обладают хорошими временными показателями, позволяя найти достаточно хорошее решение быстрее других известных детерминированных или эвристических методов.[18]

Каждая особь (генотип) представляет собой подмножество предметов, которые мы хотим упаковать в ранец (их общий вес может превысить допустимую грузоподъемность). Для удобства информация хранится в виде бинарных строк, в которых каждый бит определяет, помещается ли этот предмет в ранец[19].

Функция приспособленности определяет близость решения к оптимальному. Например, таковой может служить суммарная ценность предметов, при условии, что суммарный вес не превосходит грузоподъемность.

После серии смен поколений, в которых скрещиваются наиболее приспособленные особи и игнорируются оставшиеся, алгоритм, по предположению, должен улучшить исходные решения[19].

Частным случаем задачи рюкзака 0-1 является задача о сумме подмножеств. Пусть ${\displaystyle W}$ — грузоподъёмность рюкзака, ${\displaystyle w_{i}}$— вес ${\displaystyle i}$-го предмета, а его стоимость ${\displaystyle v_{i}=w_{i}}$. Таким образом, задача состоит в том, чтобы нагрузить рюкзак наиболее плотно, или полностью исчерпать ресурсы:

${\displaystyle W=\sum _{i=1}^{N}w_{i}x_{i},\qquad \ x_{i}\in \{0,1\}}$

Для решения можно воспользоваться упомянутым генетическим алгоритмом. Особью является вектор ${\displaystyle (x_{1},..,x_{n})}$. В качестве функции приспособленности следует использовать близость суммарного веса предметов к ${\displaystyle W}$, с той лишь особенностью, что более предпочтительны наборы, помещающиеся в рюкзак (суммарный вес предметов меньше, чем ${\displaystyle W}$)[19].

Определим формально функцию приспособленности ${\displaystyle f(x_{1},..,x_{n}):\{0,1\}^{n}\rightarrow \mathbb {R} }$. Пусть ${\displaystyle {\mathcal {S}}}$ — сумма весов всех предметов. Тогда ${\textstyle \Delta _{max}=max(W,{\mathcal {S}}-W)}$ — максимально возможное отклонение веса предметов в рюкзаке от ${\displaystyle W}$.

Пусть ${\textstyle W'=\sum _{i=1}^{N}w_{i}x_{i}}$ — суммарный вес предметов для данного вектора. Тогда положим:

${\displaystyle f(x_{1},..,x_{n})={\begin{cases}1-{\sqrt {\frac {W-W'}{W}}},&W'\leq W,\\1-{\sqrt {\frac {W'-W}{\Delta _{max}}}},&W'>W.\end{cases}}}$[19]

Пользуясь общим алгоритмом, можно найти приближенное решение:

1. Создать случайный набор особей — популяцию.
2. Подсчитать функцию приспособления для каждой особи.
3. Оставить только наиболее приспособленных особей (естественный отбор).
4. Произвести скрещивания особей.
5. Подвергнуть потомков мутации.
6. Продолжить со второго шага.

Выполнение прерывается либо при нахождении решения, либо после заданного числа итераций[19].

Благодаря тому, что задачу о рюкзаке в общем виде нельзя решить точно за приемлемое время, её можно использовать в криптографических задачах. Для этого, при публично известном наборе предметов, мы представим сообщение как набор передаваемых предметов, а отправим их суммарный вес[28].

Определение. Рюкзачным вектором ${\displaystyle A=(a_{1},...,a_{n})}$ назовём упорядоченный набор из n предметов, где ${\displaystyle a_{i}}$ — вес ${\displaystyle i}$-го предмета[30].

Рюкзачный вектор является открытым ключом. Для шифрования открытого текста его разбивают на блоки длиной ${\displaystyle n}$ бит, при этом каждый бит определяет наличие предмета в рюкзаке (например, открытый текст ${\displaystyle (111100)}$ соответствует наличию первых четырёх из шести возможных предметов в рюкзаке). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие[28].

После этого высчитывается суммарный вес предметов в рюкзаке для данного открытого текста, и передаётся в качестве шифротекста[28].

Пример шифрования данным алгоритмом:

Пусть задан рюкзачный вектор ${\displaystyle A=(3\ 4\ 6\ 7\ 10\ 11)}$ с длиной ${\displaystyle n=6}$.