Просмотр кода страницы Задача о рюкзаке

[[Файл:Knapsack.svg|thumb|right|Пример задачи о рюкзаке: необходимо уложить коробки в ранец вместимостью 15 кг так, чтобы стоимость уложенных коробок была максимальной]]
'''Задача о рюкзаке''' (также '''задача о ранце''') — [[NP-полная задача]] [[Комбинаторная оптимизация|комбинаторной оптимизации]]. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в [[Экономика|экономике]], [[Прикладная математика|прикладной математике]], [[Криптография|криптографии]] и [[Логистика|логистике]].

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

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

Математически задача формулируется следующим образом: имеется <math>n</math> грузов. Для каждого <math>i</math>-го груза определены его '''масса''' <math> w_i>0 </math> и '''ценность''' <math>v_i>0</math>, <math>i= 1,2,...,n</math>. Ограничение суммарного веса предметов в рюкзаке задаётся '''грузоподъёмностью''' <math>W</math>. Необходимо
: максимизировать <math>\sum_{i=1}^n v_i x_i</math>
: с ограничениями <math>\sum_{i=1}^n w_i x_i \leq W</math> и <math>x_i \in \{0,1\}</math> {{sfn|Silvano|1990|p=1}}.

=== Варианты задачи о рюкзаке ===
{{main|Список задач о рюкзаке}}
Постановка задачи допускает большое количество обобщений, в зависимости от условий, наложенных на рюкзак, предметы или их выбор. Наиболее популярными разновидностями являются следующие:
# Рюкзак 0-1 ({{lang-en|0-1 Knapsack Problem}}){{sfn|Silvano|1990|p=2}}: не более одного экземпляра каждого предмета.
# Ограниченный рюкзак ({{lang-en|Bounded Knapsack Problem}}){{sfn|Kellerer, Pferschy, Pisinger|2004|p=127}}: не более заданного числа экземпляров каждого предмета.
# Неограниченный рюкзак ({{lang-en|Unbounded Knapsack Problem}}){{sfn|Kellerer, Pferschy, Pisinger|2004|p=127}}: произвольное количество экземпляров каждого предмета.
# Рюкзак с мультивыбором ({{lang-en|Multiple-choice Knapsack Problem}}){{sfn|Kellerer, Pferschy, Pisinger|2004|p=147}}: предметы разделены на группы, и из каждой группы требуется выбрать только один предмет.
# Множественный рюкзак ({{lang-en|Multiple Knapsack Problem}}){{sfn|Silvano|1990|p=157}}: есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить.
# Многомерный рюкзак ({{lang-en|Multi-dimensional knapsack problem}}): вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна{{sfn|Kellerer, Pferschy, Pisinger|2004|p=147}}.
# Квадратичная задача о рюкзаке ({{lang-en|Quadratic knapsack problem}}): суммарная ценность задается неотрицательно определённой [[Квадратичная форма|квадратичной формой]]<ref>{{Статья|автор=G. Gallo, P. L. Hammer, B. Simeone|заглавие=Quadratic knapsack problems|ссылка=https://link.springer.com/chapter/10.1007/BFb0120892|язык=en|издание=Mathematical Programming Studies|тип=|год=2009|месяц=февраль|число=24|том=12|номер=|страницы=132—149|issn=0303-3929|archivedate=2016-10-24|archiveurl=https://web.archive.org/web/20161024221522/https://link.springer.com/chapter/10.1007/BFb0120892}}</ref>.

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

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

<math>\min_{x \in S} \ f(x)</math>,

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

<math>g(x) \leq b 
</math>.

Функции <math>f(x) , g(x): \mathbb{R}^n \rightarrow \mathbb{R}
</math> предполагаются [[Непрерывная функция|непрерывными]] и [[Дифференцируемая функция|дифференцируемыми]] на <math>\mathbb{R}^n</math>. <math> b 
</math> — [[Целое (тип данных)|целочисленная]] константа, множество <math>S
</math> непусто{{sfn|Bretthauer, Shetty|2002}}.

В случае [[Линейная функция|линейных функций]] <math>f(x) , g(x)
</math>, задача сводится к одной из классических постановок, в зависимости от множества <math>S
</math>:
* <math>S = \{0 , 1\}^n
</math> — рюкзак 0-1
* <math>S = \mathbb{N_0}^n
</math> — неограниченный рюкзак
* <math>S = \{(x_1,..,x_n) \in \mathbb{N_0}^n : x_i \leq c_i\} 
</math> — ограниченный рюкзак
Свобода в выборе функций <math>f(x) , g(x)
</math> позволяет решать более широкий класс задач, включая {{нп3|Организация производственных мощностей|организацию производственных мощностей|en|Capacity planning}}, оптимальное распределение [[Семплирование (математическая статистика)|семплов]] в [[Районированная выборка|районированной выборке]] или решение квадратичной задачи о рюкзаке{{sfn|Bretthauer, Shetty|2002}}.

== Точные методы решения ==
Как было сказано выше, задача о рюкзаке относится к классу [[NP-полная задача|NP-полных]], и для неё пока что не найден [[полиномиальный алгоритм]], решающий её за разумное время. Поэтому при решении задачи о рюкзаке необходимо выбирать между точными алгоритмами, которые неприменимы для «больших» рюкзаков, и приближенными, которые работают быстро, но не гарантируют оптимального решения задачи.
[[Файл:Дерево полного перебора.png|мини|Дерево полного перебора, соответствующее поиску решения для трех предметов. В каждом узле определяется, будет ли данный предмет уложен в рюкзак. Цифра в узле соответствует номеру предмета. Цифры на рёбрах: 0 означает, что предмет не был взят, 1 — что был]]

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

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

Для каждого предмета существует 2 варианта: предмет кладётся в рюкзак либо предмет не кладётся в рюкзак. Тогда перебор всех возможных вариантов имеет [[Временная сложность|временну́ю сложность]] <math> O(2^ N) </math>, что позволяет его использовать лишь для небольшого количества предметов{{sfn|Окулов|2007|pp=92—93}}.
С ростом числа предметов задача становится неразрешимой данным методом за приемлемое время.

На рисунке показано дерево перебора для трёх предметов. Каждый [[Дерево (теория графов)|лист]] соответствует некоторому подмножеству предметов. После составления дерева необходимо найти лист с максимальной ценностью среди тех, вес которых не превышает <math> W </math>{{sfn|Окулов|2007|pp=101—105}}.

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

Оригинальный алгоритм, предложенный Питером Колесаром ({{lang-en|Peter Kolesar}}) в 1967 году, предлагает отсортировать предметы по их удельной стоимости (отношению ценности к весу) и строить дерево [[Полный перебор|полного перебора]]. Его улучшение заключается в том, что в процессе построения дерева для каждого узла оценивается [[Точная верхняя и нижняя границы|верхняя граница]] ценности решения, и продолжается построение дерева только для узла с максимальной оценкой<ref name=":4" />. Когда максимальная верхняя граница оказывается в листе дерева, алгоритм заканчивает свою работу.

Способность метода ветвей и границ уменьшать количество вариантов перебора сильно опирается на входные данные. Его целесообразно применять, только если удельные ценности предметов значительно отличаются{{sfn|Бурков, Горгидзе, Ловецкий|1974|страницы=225}}.

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

==== Задача о неограниченном рюкзаке ====
При дополнительном ограничении на веса предметов, задачу о рюкзаке можно решить за [[Псевдополиномиальный алгоритм|псевдополиномиальное]] время методами [[Динамическое программирование|динамического программирования]].

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

Для <math>m[w]</math> можно записать [[Рекуррентная формула|рекуррентные формулы]]:
* <math>m[0]=0</math>
* <math>m[w]= \max_{w_i \le w}(v_i+m[w-w_i])</math><ref name=":2" />,
где <math>v_i, w_i</math> — ценность и вес <math>i</math>-го предмета соответственно, а максимум из пустого множества следует считать равным нулю.

Фактически последнее уравнение является [[Уравнение Беллмана|функциональным уравнением Р. Беллмана]] или функциональным уравнением динамического программирования. В данном случае для его решения достаточно вычислить все значения <math>m[w]</math>, начиная с <math>0</math> и до <math>W</math><ref name=":2">{{Книга|автор=Романовский И.В.|заглавие=Алгоритмы решения экстремальных задач|ссылка=https://archive.org/details/libgen_00123853|ответственный=|издание=|место=|издательство=Наука|год=1977|страницы=[https://archive.org/details/libgen_00123853/page/n252 252]-259|страниц=352|isbn=}}</ref>. Если дополнительно хранить на каждом шаге набор предметов, который реализует максимальную ценность, то алгоритм выдаст и оптимальный набор предметов.

Так как на каждом шаге необходимо найти максимум из <math>n</math> предметов, алгоритм имеет вычислительную сложность <math>O(nW)
</math>. Поскольку <math>W</math> может зависеть экспоненциально от размера входных данных, алгоритм является [[Псевдополиномиальный алгоритм|псевдополиномиальным]]. Поэтому эффективность данного алгоритма определяется значением <math>W</math>. Алгоритм даёт отличные результаты при <math>W \leq 1000</math>, но не очень хорошие для <math>W \geq 10\ 000\ 000</math><ref>{{Книга|автор=Стивен С. Скиена|заглавие=Алгоритмы. Руководство по разработке|ссылка=https://archive.org/details/algoritmyrukovod0000unse/page/n451|ответственный=|издание=2-e|место=СПб|издательство=БХВ-Петербург|год=2011|страницы=448—451|страниц=720|isbn=978-5-9775-0560-4}}</ref>.

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

[[Уравнение Беллмана|Рекуррентные соотношения]]:
* <math>m[0 , w]=0</math>
* <math>m[i,\,w]=m[i-1,\,w]</math>, если <math>w_i > w</math>
* <math>m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+v_i)</math>, если <math>w_i \leq w</math>
Вычисляя <math>m[n , W]</math>, можно найти точное решение. Если массив <math>m[i , w]</math> помещается в памяти машины, то данный алгоритм, вероятно, является одним из наиболее эффективных<ref name=":2" />.<syntaxhighlight lang="c" line="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])
</syntaxhighlight>
[[Файл:Динамическое програмирование.png|thumb|450px|Сеть, иллюстрирующая наполнение рюкзака. В квадратных скобках указаны суммарная ценность на данном шаге алгоритма, оптимальное решение помечено кругом]]
Проиллюстрировать решение методом динамического программирования можно следующим образом: на двумерной плоскости по оси <math> X </math> откладывается количество предметов, по оси <math> Y </math> — их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось <math> Y </math> равны весу предмета. На втором шаге опять строятся 2 линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Положим длину горизонтальных дуг равной нулю, а наклонных — ценности предмета{{sfn|Новиков|2001|страницы=12}}. Таким образом, любому решению задачи соответствует некоторый путь в построенном [[Дерево (теория графов)|дереве]]. Задача сводится к нахождению пути максимальной длины{{sfn|Новиков|2001|страницы=12}}.
Пусть вместимость рюкзака <math> W=14 </math>.
{| class="wikitable"
|-
! Номер предмета !! Ценность !! Вес
|-
| 1 || 3 || 5
|-
| 2 || 5 || 10
|-
| 3 || 4 || 6
|-
| 4 || 2 || 5
|}
Из рисунка видно, что суммарная ценность для оптимального решения равна 7, так как это максимальная ценность в построенном дереве.

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

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

<math>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}</math>,

с [[Начальные и граничные условия|начальными условиями]]:

<math>y[0, 0]=0</math>

<math>y[0, V]=W+1</math>{{sfn|Kellerer, Pferschy, Pisinger|2004}}

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

=== Жадный алгоритм ===
Для решения задачи [[Жадный алгоритм|жадным алгоритмом]] необходимо отсортировать вещи по их удельной ценности (то есть отношению ценности предмета к его весу), и поместить в рюкзак предметы с наибольшей удельной ценностью<ref name=":4">{{Книга|автор=Martello S., Toth P.|заглавие=Knapsack problems: algorithms and computer implementations|ссылка=https://archive.org/details/knapsackproblems0000mart|ответственный=|издание=|место=|издательство=John Wiley & Sons Ltd.|год=1990|страницы=[https://archive.org/details/knapsackproblems0000mart/page/29 29],50|страниц=296|isbn=0-471-92420-2}}</ref>.

Время работы данного алгоритма складывается из времени [[сортировки]] и времени укладки. [[Вычислительная сложность|Сложность]] сортировки предметов составляет <math> O(N\log (N)) </math>. Далее происходит вычисление того, сколько предметов поместится в рюкзак за общее время <math> O(N) </math><ref name=":4" />. Итоговая сложность <math> O(N\log (N)) </math> при необходимости сортировки и <math> O(N) </math> при уже отсортированных данных<ref name=":4" />.

'''Пример'''. Пусть вместимость рюкзака <math> W=80 </math>. Предметы уже отсортированы по удельной ценности. Применим жадный алгоритм.
{| class="wikitable" style="text-align:right;"
|-
! 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 % от ценности оптимального<ref name=":4" />.

Впервые жадный алгоритм был предложен [[Данциг, Джордж|Джорджем Данцигом]]<ref>{{source|Q28035735|ref=Dantzig|ref-year=1957}} <!-- Discrete-Variable Extremum Problems // Oper. Res. --></ref> для решения задачи о неограниченном рюкзаке.

=== Приближенная схема полностью полиномиального времени ===
Так как точного алгоритма решения задачи за [[полиномиальное время]] не было найдено, появилась задача получить полиномиальное решение с гарантированной точностью <math>1-\varepsilon</math>. Для этого существует целый ряд [[Приближенная схема полиномиального времени|приближённых схем полностью полиномиального времени]], то есть со сложностью, являющейся полиномом от <math>n</math> и <math>\frac{1}{\varepsilon}</math>.

Идея, стоящая за классической схемой, заключается в снижении точности, с которой заданы ценности предметов. Объединяя предметы близкой ценности в одну группу, можно снизить количество разных предметов. Алгоритм записывается следующим образом{{sfn|Kellerer, Pferschy, Pisinger|2004}}:
# Найдём приближённое решение <math>x^ l</math> при помощи жадного алгоритма. Пусть <math>x^*</math> — точное решение. Тогда из оценки эффективности жадного алгоритма <math>x^l \leq x^* \leq 2x^l</math>.
# Отмасштабируем ценности следующим образом: <math>v'_i = \left \lfloor \frac{v_i}{\frac{x^l\varepsilon}{n}} \right \rfloor</math>.
# Алгоритмом динамического программирования для задачи с целочисленными ценностями предметов находим решение.
Существует множество различных схем аппроксимации. Тем не менее, они сильно зависят от формулировки задачи о рюкзаке. Например, если в условии появляется второе ограничение типа неравенства (двухмерный рюкзак), то задача уже не имеет известной схемы полиномиального времени<ref>{{Статья|автор=Ariel Kulik, Hadas Shachnai|заглавие=There is no EPTAS for two-dimensional knapsack|ссылка=http://www.sciencedirect.com/science/article/pii/S0020019010001626|издание=Information Processing Letters|год=2010-07-31|том=110|выпуск=16|страницы=707–710|doi=10.1016/j.ipl.2010.05.031}}</ref>.

=== Генетические алгоритмы ===
[[Файл:Knapsack ga.svg|мини|Пример эволюции популяции при использовании генетического алгоритма. Объектами являются строчки, кодирующие в бинарном виде какие объекты кладутся в рюкзак. Например, строчка (0,1,0,1,0) соответствует выбору коробок весами 12 кг и 7 кг]]
Как и для других NP-трудных задач оптимизации, для решения задачи о рюкзаке применяются [[Генетический алгоритм|генетические алгоритмы]]. Они не гарантируют нахождения оптимального решения за [[полиномиальное время]] и не дают оценку близости решения к оптимальному, но обладают хорошими временными показателями, позволяя найти ''достаточно хорошее'' решение быстрее других известных [[Детерминированный алгоритм|детерминированных]] или [[Эвристический алгоритм|эвристических]] методов.<ref>{{Книга|автор=Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин|заглавие=Применение генетических алгоритмов к решению задач дискретной оптимизации|ссылка=http://www.unn.ru/pages/e-library/aids/2007/15.pdf|ответственный=|издание=2007|место=Нижний Новгород|издательство=|год=|страницы=|страниц=|isbn=|archivedate=2016-02-22|archiveurl=https://web.archive.org/web/20160222001039/http://www.unn.ru/pages/e-library/aids/2007/15.pdf}}</ref>

Каждая особь ([[Генетический алгоритм#Описание алгоритма|генотип]]) представляет собой подмножество предметов, которые мы хотим упаковать в ранец (их общий вес может превысить допустимую грузоподъемность). Для удобства информация хранится в виде бинарных строк, в которых каждый бит определяет, помещается ли этот предмет в ранец<ref name=":0" />.

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

После серии смен поколений, в которых [[Генетический алгоритм#.D0.A0.D0.B0.D0.B7.D0.BC.D0.BD.D0.BE.D0.B6.D0.B5.D0.BD.D0.B8.D0.B5 .28.D0.A1.D0.BA.D1.80.D0.B5.D1.89.D0|скрещиваются]] наиболее приспособленные особи и игнорируются оставшиеся, алгоритм, по предположению, должен улучшить исходные решения<ref name=":0" />.

==== Решение задачи о сумме подмножеств ====
Частным случаем задачи рюкзака 0-1 является [[задача о сумме подмножеств]]. Пусть <math>W</math> — грузоподъёмность рюкзака, <math>w_i</math>— вес <math>i</math>-го предмета, а его стоимость <math>v_i = w_i</math>. Таким образом, задача состоит в том, чтобы нагрузить рюкзак наиболее плотно, или полностью исчерпать ресурсы:

<math>W = \sum_{i=1}^N w_i x_i,  \qquad \ x_i \in \{0 , 1\}</math>

Для решения можно воспользоваться упомянутым [[Генетический алгоритм|генетическим алгоритмом]]. Особью является вектор <math>(x_1,..,x_n)</math>. В качестве функции приспособленности следует использовать близость суммарного веса предметов к <math>W</math>, с той лишь особенностью, что более предпочтительны наборы, помещающиеся в рюкзак (суммарный вес предметов меньше, чем <math>W</math>)<ref name=":0">{{Статья|автор=С. М. Авдошин, А. А. Савельева.|заглавие=Криптоанализ: современное состояние и перспективы развития|ссылка=https://www.hse.ru/data/194/314/1234/%D0%90%D0%B2%D0%B4%D0%BE%D1%88%D0%B8%D0%BD.%D0%A1%D0%B0%D0%B2%D0%B5%D0%BB%D1%8C%D0%B5%D0%B2%D0%B0_%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7.pdf|язык=ru|издание=|тип=|год=|месяц=|число=|том=|номер=|страницы=38|issn=|archivedate=2016-03-17|archiveurl=https://web.archive.org/web/20160317202725/https://www.hse.ru/data/194/314/1234/%D0%90%D0%B2%D0%B4%D0%BE%D1%88%D0%B8%D0%BD.%D0%A1%D0%B0%D0%B2%D0%B5%D0%BB%D1%8C%D0%B5%D0%B2%D0%B0_%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7.pdf}}</ref>.

Определим формально функцию приспособленности <math>f(x_1,..,x_n): \{0,1\}^n \rightarrow \mathbb{R}</math>. Пусть <math>\mathcal{S}</math> — сумма весов всех предметов. Тогда <math display="inline">\Delta_{max} = max(W, \mathcal{S}-W)</math> — максимально возможное отклонение веса предметов в рюкзаке от <math>W</math>.

Пусть <math display="inline">W' = \sum_{i=1}^N w_i x_i</math> — суммарный вес предметов для данного вектора. Тогда положим:

<math>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}</math><ref name=":0" />

Пользуясь общим алгоритмом, можно найти приближенное решение:
# Создать случайный набор особей — популяцию.
# Подсчитать функцию приспособления для каждой особи.
# Оставить только наиболее приспособленных особей (естественный отбор).
# Произвести скрещивания особей.
# Подвергнуть потомков мутации.
# Продолжить со второго шага.
Выполнение прерывается либо при нахождении решения, либо после заданного числа итераций<ref name=":0" />.

== Приложения ==
Доподлинно неизвестно, кто первым привел математическую формулировку задачи о рюкзаке. Одно из первых упоминаний о ней можно найти в статье {{нп3|Мэтьюс, Джордж Баллард|Джорджа Балларда Мэтьюса|en|George Ballard Mathews}}<ref name="Mathews">{{статья|автор=G. B. Mathews|заглавие=On the partition of numbers|ссылка=http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf|язык=en|издательство=|год=1897|pages=486—490|isbn=|allpages=|archivedate=2012-05-26|archiveurl=https://web.archive.org/web/20120526165606/http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf}}</ref>{{sfn|Kellerer, Pferschy, Pisinger|2004|p=3}}, датированной 1897 годом. Интенсивное изучение данной проблемы началось после публикации [[Данциг, Джордж|Д. Б Данцигом]] в 1957 году книги «{{lang-en|Discrete Variable Extremum Problem}}»{{sfn|Kellerer, Pferschy, Pisinger|2004|p=9}}, особенно в 70—90-е годы XX века, как теоретиками, так и практиками{{sfn|Silvano|1990|p=2}}. Во многом интерес был вызван достаточно простой формулировкой задачи, большим числом её разновидностей и свойств и в то же время сложностью их решения. В 1972 году данная задача вошла в список [[Карп, Ричард Мэннинг|М. Карпа]] [[NP-полная задача|NP-полных задач]] (статья {{lang-en|«Reducibility Among Combinatorial Problems»}})<ref name="Karp">{{статья|автор=Р. Карп|заглавие=Reducibility Among Combinatorial Problems|ссылка=http://www.cs.berkeley.edu/~luca/cs172/karp.pdf|язык=en|издательство=|год=1972|pages=|isbn=|allpages=|archivedate=2011-06-29|archiveurl=https://web.archive.org/web/20110629023717/http://www.cs.berkeley.edu/~luca/cs172/karp.pdf}}</ref>.

Наглядная интерпретация задачи о рюкзаке привела к тому, что она нашла применение в разных областях знаний: в математике, информатике и на стыке этих наук — в [[криптография|криптографии]]. В одной из работ по [[Компьютерная лингвистика|вычислительной лингвистике]]{{sfn|Riedhammer et al|2008|pp=2436|name=Riedhammer2008}} предложена формулировка задачи [[Автоматическое реферирование|автоматического реферирования текстов]], частный случай которой соответствует постановке задачи о рюкзаке.

На основе задачи о рюкзаке был создан первый алгоритм [[Криптосистема с открытым ключом|асимметричного шифрования]]. Впервые идея криптографии с открытыми ключами была представлена [[Уитфилд Диффи|Уитфилдом Диффи]] и [[Хеллман, Мартин|Мартином Хеллманом]] на Национальной компьютерной конференции ({{lang-en|National Computer Conference}}) 1976 года{{sfn|Шнаер|2002|p=19.2}}{{sfn|Габидулин, Кшевецкий, Колыбельников|2011}}.

Также задача о рюкзаке может служить моделью для большого числа промышленных задач{{sfn|Silvano|1990|p=2}}{{sfn|Бурков, Горгидзе, Ловецкий|1974|p=217}}:
* Размещение грузов на складе минимальной площади.
* [[Задача раскроя|Раскройка]] ткани — из имеющегося куска материала получить максимальное число выкроек определённой формы.
* Расчет оптимальных [[Капиталовложение|капиталовложений]].

== Задача о рюкзаке в криптографии ==
{{main|Задача о рюкзаке в криптографии}}
В 1978 году Ральф Меркл и Мартин Хеллман разработали первый алгоритм для обобщённого шифрования с [[Криптосистема с открытым ключом|открытым ключом]] — '''[[ранцевая криптосистема Меркла — Хеллмана|криптосистему Меркла — Хеллмана]],''' построив её на основе задачи о ранце. Они опубликовали одностадийный ({{lang-en|singly-iterated}}) и мультистадийный ({{lang-en|multiply-iterated}}) варианты, а алгоритм мог быть использован только для шифрования. Но [[Шамир, Ади|Ади Шамир]] адаптировал его и для использования в [[Электронная цифровая подпись|цифровых подписях]]{{sfn|Шнаер|2002|p=19.1}}.

В дальнейшем были предложены и другие криптосистемы на основе задачи о рюкзаке, часть из которых являются модификацией криптосистемы Меркла — Хеллмана. Известные криптосистемы<ref name="Kin">{{статья|автор=Kin Ming Lai.|заглавие=Knapsack Cryptosystems: The Past and the Future|ссылка=http://www.ics.uci.edu/~mingl/knapsack.html|язык=ru|издательство=|год=2001|pages=|isbn=|allpages=|archivedate=2012-11-17|archiveurl=https://web.archive.org/web/20121117131716/http://www.ics.uci.edu/~mingl/knapsack.html}}</ref>:
* Рюкзак Грэма — Шамира
* Рюкзак Гудмана — Маколи
* Рюкзак Наккаша — Стерна
* Рюкзак Шора — Ривеста

=== Шифрование с помощью задачи о рюкзаке ===
Благодаря тому, что задачу о рюкзаке в общем виде нельзя решить точно за приемлемое время, её можно использовать в [[Криптография|криптографических]] задачах. Для этого, при публично известном наборе предметов, мы представим сообщение как набор передаваемых предметов, а отправим их суммарный вес{{sfn|Шнаер|2002|p=19.1}}.

'''Определение.''''' Рюкзачным вектором'' <math> A = (a_1,...,a_n)</math> назовём упорядоченный набор из n предметов, где <math> a_i</math> — вес <math> i</math>-го предмета{{sfn|Саломаа|1995|p=103}}.

Рюкзачный вектор является [[Открытый ключ|открытым ключом]]. Для шифрования [[Открытый текст|открытого текста]] его разбивают на блоки длиной <math>n</math> бит, при этом каждый бит определяет наличие предмета в рюкзаке (например, открытый текст <math>(1 1 1 1 0 0)</math> соответствует наличию первых четырёх из шести возможных предметов в рюкзаке). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие{{sfn|Шнаер|2002|p=19.1}}.

После этого высчитывается суммарный вес предметов в рюкзаке для данного открытого текста, и передаётся в качестве [[шифротекст]]а{{sfn|Шнаер|2002|p=19.1}}[[Шифротекст|.]]

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

Пусть задан рюкзачный вектор <math> A = (3\ 4\ 6\ 7\ 10\ 11)</math> с длиной <math>n=6</math>.
{| class="wikitable"
|-
! Открытый текст !! 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
|}

{{rq|topic=IT|sources}}

== Примечания ==
{{примечания|2}}

== Литература ==
'''на русском языке'''
# {{source|Q21694522|ref=Левитин|ref-year=2006|pages=160—163}} <!-- Алгоритмы. Введение в разработку и анализ -->
# {{книга
|автор = Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн
|заглавие = Алгоритмы: построение и анализ
|оригинал = Introduction to Algorithms
|ссылка = http://e-maxx.ru/bookz/files/cormen.pdf
|место = М.
|издание = 2-е
|издательство = [[Вильямс (издательство)|«Вильямс»]]
|год = 2006
|страницы = 456—458
|isbn = 0-07-013151-1
}}
# {{книга
|автор = [[Роберт Седжвик]]
|заглавие = Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск
|оригинал = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching
|место = Россия, Санкт-Петербург
|издание = 3-е
|издательство = [[DiaSoft (издательство)|«ДиаСофт»]]
|год = 2002
|страницы = 688
|isbn = 5-93772-047-4, 0-201-35088-2
}}
# {{source|Q27986347|ref=Бурков, Горгидзе, Ловецкий|ref-year=1974}} <!-- Прикладные задачи теории графов -->
# {{книга
|автор = В. Н. Бурков, Д. А. Новиков.
|заглавие = Элементы теории графов
|ссылка = http://www.mtas.ru/start/t_garf.pdf
|год = 2001
|страницы = 28
|ref = Новиков
}}
# {{книга
|автор = С. Окулов.
|заглавие = Программирование в алгоритмах
|ссылка = https://content.schools.by/3.orsha/library/Окулов_Программирование_в_алгоритмах.pdf
|издание = 1-е
|издательство = Бином. Лаборатория знаний
|год = 2007
|страницы = 384
|isbn = 5-94774-010-9
|ref           = Окулов
}}
# {{книга
|автор = Б. Шнайер.
|заглавие = Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си
|оригинал = Applied Cryptography. Protocols, Algorithms, and Source Code in C
|ссылка = http://htrd.su/wiki/_media/zhurnal/2012/03/23/todo_prikladnaja_kriptografija/cryptoshn.pdf
|издание = 2-е
|издательство = Триумф
|год = 2002
|страниц = 816
|isbn = 5-89392-055-4
|тираж = 3000
|ref = Шнаер
}} {{Wayback|url=http://htrd.su/wiki/_media/zhurnal/2012/03/23/todo_prikladnaja_kriptografija/cryptoshn.pdf |date=20181218010928 }}
# {{книга
 |автор               = А. Саломаа.
 |заглавие         = Криптография с открытым ключом
 |оригинал         = Public-Key Cryptography
 |ссылка             = http://tcode.tinro.ru/cryptography/src/open_key_crypt.pdf
 |место               = М.
 |издательство = Мир
 |год                   = 1995
 |страницы         = 102—150
 |isbn                     = 5–03–001991–X
 |ref                      = Саломаа
}} {{Wayback|url=http://tcode.tinro.ru/cryptography/src/open_key_crypt.pdf |date=20160304204604 }}
# {{книга
|автор =Н. Коблиц.
|заглавие = Курс теории чисел в криптографии
|место = М.
|издание = 2-е
|издательство = Научное издательство ТВП
|год = 2001
|страницы = 254
|isbn = 5-85484-014-6
|ref           = Коблиц
}}
# {{source|Q26887236|ref=Габидулин, Кшевецкий, Колыбельников|ref-year=2011}}
# {{статья
|автор         = Осипян В. О.
|заглавие      = О системе защиты информации на основе проблемы рюкзака
|ссылка        = http://earchive.tpu.ru/handle/11683/1095
|издание       = Известия Томского политехнического университета [Известия ТПУ]
|год           = 2006
|том           = 309
|номер         = 2
|страницы      = 209—212
}} <!-- Защита информации -->

'''на английском языке'''
# {{книга
 |автор         = Silvano Martelo, Paolo Toth
 |заглавие      = Knapsack problems
 |ссылка        = http://www.or.deis.unibo.it/kp/Chapter1.pdf
 |место         = Great Britain
 |издательство  = Wiley
 |год           = 1990
 |страниц       = 306
 |isbn          = 0-471-92420-2
 |ref           = Silvano
}}
# {{source|Q28035673|ref=Kellerer, Pferschy, Pisinger|ref-year=2004}} <!-- Knapsack Problems -->
# {{статья
|автор =K. Riedhammer, D. Gillick, B. Favre, and D. Hakkani-Tür
|заглавие = Packing the Meeting Summarization Knapsack
|ссылка = http://www5.informatik.uni-erlangen.de/Forschung/Publikationen/2008/Riedhammer08-PTM.pdf
|издательство=Proc. Interspeech, Brisbane, Australia
|место = Brisbane Australia
|год = 2008
|страниц = 4
|ref = Riedhammer et al
}}
# {{source|Q27986324|ref=Bretthauer, Shetty|ref-year=2002}} <!-- The nonlinear knapsack problem — algorithms and applications // European Journal of Operational Research -->

== Ссылки ==
* [http://www.ifors.ms.unimelb.edu.au/tutorial/knapsack/index.html Welcome to the Knapsack]{{ref-en}}
* [http://www.academicearth.org/lectures/knapsack-problem-1 Knapsack Problem By Eric Grimsom John Guttag — MIT]{{ref-en}}
* [http://rosettacode.org/wiki/Knapsack_Problem Knapsack Problem solutions in many languages]{{ref-en}}
* [http://www.proggen.org/doku.php?id=algo:knapsack Das Rucksack-Problem (Knapsack Problem)]{{ref-de}}

{{Knapsack}}
{{NP-полные задачи}}

{{Хорошая статья|Математика}}


[[Категория:Прикладная математика]]
[[Категория:Динамическое программирование]]
[[Категория:Рюкзаки]]