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

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

Пример задачи о рюкзаке: необходимо уложить коробки в ранец вместимостью 15 кг так, чтобы стоимость уложенных коробок была максимальной

В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.

Классическая постановка задачиПравить

Пусть имеется набор предметов, каждый из которых имеет два параметра — масса и ценность. Также имеется рюкзак определённой грузоподъёмности. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом ограничение рюкзака на суммарную массу.

Математически задача формулируется следующим образом: имеется $n$$n$  грузов. Для каждого $i$$i$ -го груза определены его масса $w_i>0$$w_{i}>0$  и ценность $v_i>0$$v_{i}>0$ , $i=1,2,...,n$$i=1,2,...,n$ . Ограничение суммарного веса предметов в рюкзаке задаётся грузоподъёмностью $W$$W$ . Необходимо

максимизировать $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{v}_i{x}_i$$\sum _{i=1}^{n}v_{i}x_{i}$ 

с ограничениями $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{w}_i{x}_i\le <!--\; \le \; -->W$$\sum _{i=1}^{n}w_{i}x_{i}\leq W$  и $x_i\in <!--\; \in \; -->\{0,1\}$$x_{i}\in \{0,1\}$  .

Варианты задачи о рюкзакеПравить

Основная статья: Список задач о рюкзаке

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

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

Нелинейная задача о рюкзакеПравить

Одним из наиболее общих вариантов задачи о рюкзаке является нелинейный. Его можно сформулировать следующим образом:

Пусть вектор $x=(x_1,..,x_n)\in <!--\; \in \; -->{\mathbb{R}}^n$$x=(x_{1},..,x_{n})\in \mathbb {R} ^{n}$  определяет количество экземпляров каждого предмета в рюкзаке. Тогда задача состоит в нахождении минимума функции

$\underset{x\in <!--\; \in \; -->S}{min}f(x)$$\min _{x\in S}\ f(x)$ ,

при заданном ограничении:

$g(x)\le <!--\; \le \; -->b$$g(x)\leq b$ .

Функции $f(x),g(x):{\mathbb{R}}^n\to <!--\; \to \; -->\mathbb{R}$$f(x),g(x):\mathbb {R} ^{n}\rightarrow \mathbb {R}$  предполагаются непрерывными и дифференцируемыми на ${\mathbb{R}}^n$$\mathbb {R} ^{n}$ . $b$$b$  — целочисленная константа, множество $S$$S$  непусто.

В случае линейных функций $f(x),g(x)$$f(x),g(x)$ , задача сводится к одной из классических постановок, в зависимости от множества $S$$S$ :

• $S=\{0,1{\}}^n$$S=\{0,1\}^{n}$  — рюкзак 0-1
• $S={{\mathbb{N}}_{\mathbb{0}}}^n$$S=\mathbb {N_{0}} ^{n}$  — неограниченный рюкзак
• $S=\{(x_1,..,x_n)\in <!--\; \in \; -->{{\mathbb{N}}_{\mathbb{0}}}^n:x_i\le <!--\; \le \; -->c_i\}$$S=\{(x_{1},..,x_{n})\in \mathbb {N_{0}} ^{n}:x_{i}\leq c_{i}\}$  — ограниченный рюкзак

Свобода в выборе функций $f(x),g(x)$$f(x),g(x)$  позволяет решать более широкий класс задач, включая организацию производственных мощностей  (англ.) (рус., оптимальное распределение семплов в районированной выборке или решение квадратичной задачи о рюкзаке.

Точные методы решенияПравить

Как было сказано выше, задача о рюкзаке относится к классу NP-полных, и для неё пока что не найден полиномиальный алгоритм, решающий её за разумное время. Поэтому при решении задачи о рюкзаке необходимо выбирать между точными алгоритмами, которые неприменимы для «больших» рюкзаков, и приближенными, которые работают быстро, но не гарантируют оптимального решения задачи.

 

Дерево полного перебора, соответствующее поиску решения для трех предметов. В каждом узле определяется, будет ли данный предмет уложен в рюкзак. Цифра в узле соответствует номеру предмета. Цифры на рёбрах: 0 означает, что предмет не был взят, 1 — что был.

Полный переборПравить

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

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

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

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

Метод ветвей и границПравить

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

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

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

Методы динамического программированияПравить

Задача о неограниченном рюкзакеПравить

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

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

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

• $m[0]=0$$m[0]=0$ 
• $m[w]=\underset{w_i\le <!--\; \le \; -->w}{max}(v_i+m[w-<!--\; -\; -->w_i])$$m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])$ ,

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

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

Так как на каждом шаге необходимо найти максимум из $n$$n$  предметов, алгоритм имеет вычислительную сложность $O(nW)$$O(nW)$ . Поскольку $W$$W$  может зависеть экспоненциально от размера входных данных, алгоритм является псевдополиномиальным. Поэтому эффективность данного алгоритма определяется значением $W$$W$ . Алгоритм даёт отличные результаты при $W\le <!--\; \le \; -->1000$$W\leq 1000$ , но не очень хорошие для $W\ge <!--\; \ge \; -->10000000$$W\geq 10\ 000\ 000$ .

Задача о рюкзаке 0-1Править

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

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

• $m[0,w]=0$$m[0,w]=0$ 
• $m[i,w]=m[i-<!--\; -\; -->1,w]$$m[i,\,w]=m[i-1,\,w]$ , если $w_i>w$$w_{i}>w$ 
• $m[i,w]=max(m[i-<!--\; -\; -->1,w],m[i-<!--\; -\; -->1,w-<!--\; -\; -->w_i]+v_i)$$m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ , если $w_i\le <!--\; \le \; -->w$$w_{i}\leq w$ 

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

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

 

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

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

Номер предмета	Ценность	Вес
1	3	5
2	5	10
3	4	6
4	2	5

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

Динамическое программирование над ценностями предметовПравить

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

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

$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}}$ ,

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

$y[0,0]=0$$y[0,0]=0$ 

$y[0,V]=W+1$$y[0,V]=W+1$ 

Приближенные методы решенияПравить

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

Жадный алгоритмПравить

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

Время работы данного алгоритма складывается из времени сортировки и времени укладки. Сложность сортировки предметов составляет $O(N\log <!--\; \; -->(N))$$O(N\log(N))$ . Далее происходит вычисление того, сколько предметов поместится в рюкзак за общее время $O(N)$$O(N)$ . Итоговая сложность $O(N\log <!--\; \; -->(N))$$O(N\log(N))$  при необходимости сортировки и $O(N)$$O(N)$  при уже отсортированных данных.

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

i	вес	цена	цена/вес
1	15	60	4
2	30	90	3
3	50	100	2

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

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

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

Приближенная схема полностью полиномиального времениПравить

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

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

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

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

Генетические алгоритмыПравить

 

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

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

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

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

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

Решение задачи о сумме подмножествПравить

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

$W=\underset{i=1}{\overset{N}{\sum <!--\; \sum \; -->}}{w}_i{x}_i,x_i\in <!--\; \in \; -->\{0,1\}$$W=\sum _{i=1}^{N}w_{i}x_{i},\qquad \ x_{i}\in \{0,1\}$ 

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

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

Пусть $W^{\prime }=\underset{i=1}{\overset{N}{\sum <!--\; \sum \; -->}}{w}_i{x}_i$${\textstyle W'=\sum _{i=1}^{N}w_{i}x_{i}}$  — суммарный вес предметов для данного вектора. Тогда положим:

$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}}$ 

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

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

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

ПриложенияПравить

Доподлинно неизвестно, кто первым привел математическую формулировку задачи о рюкзаке. Одно из первых упоминаний о ней можно найти в статье Джорджа Балларда Мэтьюса  (англ.) (рус., датированной 1897 годом. Интенсивное изучение данной проблемы началось после публикации Д. Б Данцигом в 1957 году книги «англ. Discrete Variable Extremum Problem», особенно в 70—90-е годы XX века, как теоретиками, так и практиками. Во многом интерес был вызван достаточно простой формулировкой задачи, большим числом её разновидностей и свойств и в то же время сложностью их решения. В 1972 году данная задача вошла в список М. Карпа NP-полных задач (статья англ. «Reducibility Among Combinatorial Problems»).

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

На основе задачи о рюкзаке был создан первый алгоритм асимметричного шифрования. Впервые идея криптографии с открытыми ключами была представлена Уитфилдом Диффи и Мартином Хеллманом на Национальной компьютерной конференции (англ. National Computer Conference) 1976 года.

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

• Размещение грузов на складе минимальной площади.
• Раскройка ткани — из имеющегося куска материала получить максимальное число выкроек определённой формы.
• Расчет оптимальных капиталовложений.

Задача о рюкзаке в криптографииПравить

Основная статья: Задача о рюкзаке в криптографии

В 1978 году Ральф Меркл и Мартин Хеллман разработали первый алгоритм для обобщённого шифрования с открытым ключом — криптосистему Меркла — Хеллмана, построив её на основе задачи о ранце. Они опубликовали одностадийный (англ. singly-iterated) и мультистадийный (англ. multiply-iterated) варианты, а алгоритм мог быть использован только для шифрования. Но Ади Шамир адаптировал его и для использования в цифровых подписях.

В дальнейшем были предложены и другие криптосистемы на основе задачи о рюкзаке, часть из которых являются модификацией криптосистемы Меркла — Хеллмана. Известные криптосистемы:

• Рюкзак Грэма — Шамира
• Рюкзак Гудмана — Маколи
• Рюкзак Наккаша — Стерна
• Рюкзак Шора — Ривеста

Шифрование с помощью задачи о рюкзакеПравить

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

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

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

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

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

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

Открытый текст	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0 0	0 0 0 0 0 1
Вещи в рюкзаке	3 4 6 7 10	6 7		11
Шифротекст	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	11

ЛитератураПравить

на русском языке

1. Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 160—163. — 576 с. — ISBN 978-5-8459-0987-9
2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-ое. — М.: «Вильямс», 2006. — С. 456—458. — ISBN 0-07-013151-1.
3. Роберт Седжвик. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. — 3-е. — Россия, Санкт-Петербург: «ДиаСофт», 2002. — С. 688. — ISBN 5-93772-047-4, 0-201-35088-2.
4. Бурков В. Н., Горгидзе И. А., Ловецкий С. Е. Прикладные задачи теории графов / под ред. А. Я. Горгидзе — Тбилиси: Вычислительный центр АН СССР, 1974. — 231 с.
5. В. Н. Бурков, Д. А. Новиков. Элементы теории графов. — 2001. — С. 28.
6. С. Окулов. Программирование в алгоритмах. — 1-е. — Бином. Лаборатория знаний, 2007. — С. 384. — ISBN 5-94774-010-9.
7. Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms, and Source Code in C. — 2-ое. — Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4. Архивная копия от 18 декабря 2018 на Wayback Machine
8. А. Саломаа. Криптография с открытым ключом = Public-Key Cryptography. — М.: Мир, 1995. — С. 102—150. — ISBN 5–03–001991–X. Архивная копия от 4 марта 2016 на Wayback Machine
9. Н. Коблиц. Курс теории чисел в криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 254. — ISBN 5-85484-014-6.
10. Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
11. Осипян В. О. О системе защиты информации на основе проблемы рюкзака // Известия Томского политехнического университета [Известия ТПУ]. — 2006. — Т. 309, № 2. — С. 209—212.

на английском языке

1. Silvano Martelo, Paolo Toth. Knapsack problems. — Great Britain: Wiley, 1990. — 306 с. — ISBN 0-471-92420-2.
2. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems (англ.) — Springer Science+Business Media, 2004. — 548 p. — ISBN 978-3-642-07311-3 — doi:10.1007/978-3-540-24777-7
3. K. Riedhammer, D. Gillick, B. Favre, and D. Hakkani-Tür. Packing the Meeting Summarization Knapsack. — Brisbane Australia: Proc. Interspeech, Brisbane, Australia, 2008.
4. Bretthauer K. M., Shetty B. The nonlinear knapsack problem – algorithms and applications (англ.) // European Journal of Operational Research — Elsevier BV, 2002. — Vol. 138, Iss. 3. — P. 459–472. — ISSN 0377-2217; 1872-6860 — doi:10.1016/S0377-2217(01)00179-5

СсылкиПравить

• Welcome to the Knapsack (англ.)
• Knapsack Problem By Eric Grimsom John Guttag — MIT (англ.)
• Knapsack Problem solutions in many languages (англ.)
• Das Rucksack-Problem (Knapsack Problem) (нем.)