Задача о рюкзаке
Задача о рюкзаке (также задача о ранце) — NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в экономике, прикладной математике, криптографии и логистике.
В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.
Классическая постановка задачи
Пусть имеется набор предметов, каждый из которых имеет два параметра — масса и ценность. Также имеется рюкзак определённой грузоподъёмности. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом ограничение рюкзака на суммарную массу.
Математически задача формулируется следующим образом: имеется грузов. Для каждого -го груза определены его масса и ценность , . Ограничение суммарного веса предметов в рюкзаке задаётся грузоподъёмностью . Необходимо
- максимизировать
- с ограничениями и [1].
Варианты задачи о рюкзаке
Постановка задачи допускает большое количество обобщений, в зависимости от условий, наложенных на рюкзак, предметы или их выбор. Наиболее популярными разновидностями являются следующие:
- Рюкзак 0-1 (англ. 0-1 Knapsack Problem)[2]: не более одного экземпляра каждого предмета.
- Ограниченный рюкзак (англ. Bounded Knapsack Problem)[3]: не более заданного числа экземпляров каждого предмета.
- Неограниченный рюкзак (англ. Unbounded Knapsack Problem)[3]: произвольное количество экземпляров каждого предмета.
- Рюкзак с мультивыбором (англ. Multiple-choice Knapsack Problem)[4]: предметы разделены на группы, и из каждой группы требуется выбрать только один предмет.
- Множественный рюкзак (англ. Multiple Knapsack Problem)[5]: есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить.
- Многомерный рюкзак (англ. Multi-dimensional knapsack problem): вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна[4].
- Квадратичная задача о рюкзаке (англ. Quadratic knapsack problem): суммарная ценность задается неотрицательно определённой квадратичной формой[6].
Нелинейная задача о рюкзаке
Одним из наиболее общих вариантов задачи о рюкзаке является
Пусть вектор определяет количество экземпляров каждого предмета в рюкзаке. Тогда задача состоит в нахождении минимума функции
,
при заданном ограничении:
.
Функции предполагаются непрерывными и дифференцируемыми на . — целочисленная константа, множество непусто[7].
В случае линейных функций , задача сводится к одной из классических постановок, в зависимости от множества :
- — рюкзак 0-1
- — неограниченный рюкзак
- — ограниченный рюкзак
Свобода в выборе функций позволяет решать более широкий класс задач, включая организацию производственных мощностей[англ.], оптимальное распределение семплов в районированной выборке или решение квадратичной задачи о рюкзаке[7].
Точные методы решения
Как было сказано выше, задача о рюкзаке относится к классу
Полный перебор
Как и для других дискретных задач, задачу о рюкзаке можно решить, полностью перебрав все возможные решения.
По условию задачи имеется предметов, которые можно укладывать в рюкзак, и нужно определить максимальную стоимость груза, вес которого не превышает .
Для каждого предмета существует 2 варианта: предмет кладётся в рюкзак либо предмет не кладётся в рюкзак. Тогда перебор всех возможных вариантов имеет
На рисунке показано дерево перебора для трёх предметов. Каждый лист соответствует некоторому подмножеству предметов. После составления дерева необходимо найти лист с максимальной ценностью среди тех, вес которых не превышает [9].
Метод ветвей и границ
Метод ветвей и границ является вариацией метода полного перебора с той разницей, что исключаются заведомо неоптимальные ветви дерева полного перебора. Как и метод полного перебора, он позволяет найти оптимальное решение и поэтому относится к точным алгоритмам.
Оригинальный алгоритм, предложенный Питером Колесаром (англ. Peter Kolesar) в 1967 году, предлагает отсортировать предметы по их удельной стоимости (отношению ценности к весу) и строить дерево полного перебора. Его улучшение заключается в том, что в процессе построения дерева для каждого узла оценивается верхняя граница ценности решения, и продолжается построение дерева только для узла с максимальной оценкой[10]. Когда максимальная верхняя граница оказывается в листе дерева, алгоритм заканчивает свою работу.
Способность метода ветвей и границ уменьшать количество вариантов перебора сильно опирается на входные данные. Его целесообразно применять только если удельные ценности предметов значительно отличаются[11].
Методы динамического программирования
Задача о неограниченном рюкзаке
При дополнительном ограничении на веса предметов, задачу о рюкзаке можно решить за псевдополиномиальное время методами динамического программирования.
Пусть вес каждого предмета является целым положительным числом. Тогда для решения задачи необходимо вычислить оптимальные решения для всех , где — заданная грузоподъемность. Определим как максимальную ценность предметов, которые можно поместить в рюкзак грузоподъемностью .
Для можно записать рекуррентные формулы:
- [12],
где — ценность и вес -го предмета соответственно, а максимум из пустого множества следует считать равным нулю.
Фактически последнее уравнение является функциональным уравнением Р. Беллмана или функциональным уравнением динамического программирования. В данном случае для его решения достаточно вычислить все значения , начиная с и до [12]. Если дополнительно хранить на каждом шаге набор предметов, который реализует максимальную ценность, то алгоритм выдаст и оптимальный набор предметов.
Так как на каждом шаге необходимо найти максимум из предметов, алгоритм имеет вычислительную сложность . Поскольку может зависеть экспоненциально от размера входных данных, алгоритм является псевдополиномиальным. Поэтому эффективность данного алгоритма определяется значением . Алгоритм даёт отличные результаты при , но не очень хорошие для [13].
Задача о рюкзаке 0-1
Решение задачи о рюкзаке 0-1 близко к решению предыдущей задачи, но необходимо учесть тот факт, что каждый предмет имеется в единственном экземпляре. Пусть — максимальная ценность предметов, полученных из первых имеющихся предметов, с суммарным весом не превышающим .
- , если
- , если
Вычисляя , можно найти точное решение. Если массив помещается в памяти машины, то данный алгоритм, вероятно, является одним из наиболее эффективных[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])
Проиллюстрировать решение методом динамического программирования можно следующим образом: на двумерной плоскости по оси откладывается количество предметов, по оси — их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось равны весу предмета. На втором шаге опять строятся 2 линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Положим длину горизонтальных дуг равной нулю, а наклонных — ценности предмета[14]. Таким образом, любому решению задачи соответствует некоторый путь в построенном дереве. Задача сводится к нахождению пути максимальной длины[14]. Пусть вместимость рюкзака .
Номер предмета | Ценность | Вес |
---|---|---|
1 | 3 | 5 |
2 | 5 | 10 |
3 | 4 | 6 |
4 | 2 | 5 |
Из рисунка видно, что суммарная ценность для оптимального решения равна 7, так как это максимальная ценность в построенном дереве.
Динамическое программирование над ценностями предметов
После этого решим функциональное уравнение динамического программирования:
,
Приближенные методы решения
Как и для большинства NP-полных задач, не всегда необходимо получать точное решение, так как решения, близкие к оптимальным, могут применяться в прикладных задачах.
Жадный алгоритм
Для решения задачи жадным алгоритмом необходимо отсортировать вещи по их удельной ценности (то есть отношению ценности предмета к его весу), и поместить в рюкзак предметы с наибольшей удельной ценностью[10].
Время работы данного алгоритма складывается из времени
Пример. Пусть вместимость рюкзака . Предметы уже отсортированы по удельной ценности. Применим жадный алгоритм.
i | вес | цена | цена/вес |
---|---|---|---|
1 | 15 | 60 | |
2 | 30 | 90 | |
3 | 50 | 100 |
Кладём в рюкзак первый предмет, а за ним второй. Третий предмет в рюкзак не влезет. Суммарная ценность вещей в рюкзаке равна 150. Если бы были взяты второй и третий предметы, то суммарная ценность составила бы 190. Таким образом, мы получили некоторое неоптимальное решение.
Следует понимать, что жадный алгоритм может привести к ответу сколь угодно далёкому от оптимального. Например, если один предмет имеет вес 1 и стоимость 2, а другой — вес W и стоимость W, то жадный алгоритм наберёт итоговую стоимость 2 при оптимальном ответе W. При этом тот же алгоритм для неограниченной задачи о рюкзаке приведёт к ответу, составляющему не менее 50 % от ценности оптимального[10].
Впервые жадный алгоритм был предложен Джорджем Данцигом[16] для решения задачи о неограниченном рюкзаке.
Приближенная схема полностью полиномиального времени
Так как точного алгоритма решения задачи за
Идея, стоящая за классической схемой, заключается в снижении точности, с которой заданы ценности предметов. Объединяя предметы близкой ценности в одну группу, можно снизить количество разных предметов. Алгоритм записывается следующим образом[15]:
- Найдём приближённое решение при помощи жадного алгоритма. Пусть — точное решение. Тогда из оценки эффективности жадного алгоритма .
- Отмасштабируем ценности следующим образом: .
- Алгоритмом динамического программирования для задачи с целочисленными ценностями предметов находим решение.
Существует множество различных схем аппроксимации. Тем не менее, они сильно зависят от формулировки задачи о рюкзаке. Например, если в условии появляется второе ограничение типа неравенства (двухмерный рюкзак), то задача уже не имеет известной схемы полиномиального времени[17].
Генетические алгоритмы
Как и для других NP-трудных задач оптимизации, для решения задачи о рюкзаке применяются
Каждая особь (генотип) представляет собой подмножество предметов, которые мы хотим упаковать в ранец (их общий вес может превысить допустимую грузоподъемность). Для удобства информация хранится в виде бинарных строк, в которых каждый бит определяет, помещается ли этот предмет в ранец[19].
Функция приспособленности определяет близость решения к оптимальному. Например, таковой может служить суммарная ценность предметов, при условии, что суммарный вес не превосходит грузоподъемность.
После серии смен поколений, в которых скрещиваются наиболее приспособленные особи и игнорируются оставшиеся, алгоритм, по предположению, должен улучшить исходные решения[19].
Решение задачи о сумме подмножеств
Частным случаем задачи рюкзака 0-1 является задача о сумме подмножеств. Пусть — грузоподъёмность рюкзака, — вес -го предмета, а его стоимость . Таким образом, задача состоит в том, чтобы нагрузить рюкзак наиболее плотно, или полностью исчерпать ресурсы:
Для решения можно воспользоваться упомянутым генетическим алгоритмом. Особью является вектор . В качестве функции приспособленности следует использовать близость суммарного веса предметов к , с той лишь особенностью, что более предпочтительны наборы, помещающиеся в рюкзак (суммарный вес предметов меньше, чем )[19].
Определим формально функцию приспособленности . Пусть — сумма весов всех предметов. Тогда — максимально возможное отклонение веса предметов в рюкзаке от .
Пусть — суммарный вес предметов для данного вектора. Тогда положим:
Пользуясь общим алгоритмом, можно найти приближенное решение:
- Создать случайный набор особей — популяцию.
- Подсчитать функцию приспособления для каждой особи.
- Оставить только наиболее приспособленных особей (естественный отбор).
- Произвести скрещивания особей.
- Подвергнуть потомков мутации.
- Продолжить со второго шага.
Выполнение прерывается либо при нахождении решения, либо после заданного числа итераций[19].
Приложения
Доподлинно неизвестно, кто первым привел математическую формулировку задачи о рюкзаке. Одно из первых упоминаний о ней можно найти в статье Джорджа Балларда Мэтьюса[англ.][20][21], датированной 1897 годом. Интенсивное изучение данной проблемы началось после публикации Д. Б Данцигом в 1957 году книги «англ. Discrete Variable Extremum Problem»[22], особенно в 70—90-е годы XX века, как теоретиками, так и практиками[2]. Во многом интерес был вызван достаточно простой формулировкой задачи, большим числом её разновидностей и свойств и в то же время сложностью их решения. В 1972 году данная задача вошла в список М. Карпа NP-полных задач (статья англ. «Reducibility Among Combinatorial Problems»)[23].
Наглядная интерпретация задачи о рюкзаке привела к тому, что она нашла применение в разных областях знаний: в математике, информатике и на стыке этих наук — в криптографии. В одной из работ по вычислительной лингвистике[24] предложена формулировка задачи автоматического реферирования текстов, частный случай которой соответствует постановке задачи о рюкзаке.
На основе задачи о рюкзаке был создан первый алгоритм
Также задача о рюкзаке может служить моделью для большого числа промышленных задач[2][27]:
- Размещение грузов на складе минимальной площади.
- Раскройка ткани — из имеющегося куска материала получить максимальное число выкроек определённой формы.
- Расчет оптимальных капиталовложений.
Задача о рюкзаке в криптографии
В 1978 году Ральф Меркл и Мартин Хеллман разработали первый алгоритм для обобщённого шифрования с
В дальнейшем были предложены и другие криптосистемы на основе задачи о рюкзаке, часть из которых являются модификацией криптосистемы Меркла — Хеллмана. Известные криптосистемы[29]:
- Рюкзак Грэма — Шамира
- Рюкзак Гудмана — Маколи
- Рюкзак Наккаша — Стерна
- Рюкзак Шора — Ривеста
Шифрование с помощью задачи о рюкзаке
Благодаря тому, что задачу о рюкзаке в общем виде нельзя решить точно за приемлемое время, её можно использовать в криптографических задачах. Для этого, при публично известном наборе предметов, мы представим сообщение как набор передаваемых предметов, а отправим их суммарный вес[28].
Определение. Рюкзачным вектором назовём упорядоченный набор из n предметов, где — вес -го предмета[30].
Рюкзачный вектор является
После этого высчитывается суммарный вес предметов в рюкзаке для данного открытого текста, и передаётся в качестве шифротекста[28].
Пример шифрования данным алгоритмом:
Пусть задан рюкзачный вектор с длиной .
Открытый текст | 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 |
Примечания
- ↑ Silvano, 1990, p. 1.
- ↑ 1 2 3 Silvano, 1990, p. 2.
- ↑ 1 2 Kellerer, Pferschy, Pisinger, 2004, p. 127.
- ↑ 1 2 Kellerer, Pferschy, Pisinger, 2004, p. 147.
- ↑ Silvano, 1990, p. 157.
- ISSN 0303-3929. Архивировано24 октября 2016 года.
- ↑ 1 2 Bretthauer, Shetty, 2002.
- ↑ Окулов, 2007, pp. 92—93.
- ↑ Окулов, 2007, pp. 101—105.
- ↑ 1 2 3 4 5 Martello S., Toth P. Knapsack problems: algorithms and computer implementations. — John Wiley & Sons Ltd., 1990. — С. 29,50. — 296 с. — ISBN 0-471-92420-2.
- ↑ Бурков, Горгидзе, Ловецкий, 1974, с. 225.
- ↑ 1 2 3 Романовский И.В. Алгоритмы решения экстремальных задач. — Наука, 1977. — С. 252-259. — 352 с.
- ↑ Стивен С. Скиена. Алгоритмы. Руководство по разработке. — 2-e. — СПб.: БХВ-Петербург, 2011. — С. 448—451. — 720 с. — ISBN 978-5-9775-0560-4.
- ↑ 1 2 Новиков, 2001, с. 12.
- ↑ 1 2 Kellerer, Pferschy, Pisinger, 2004.
- ↑ Dantzig G. B. Discrete-Variable Extremum Problems (англ.) // Operations Research — Institute for Operations Research and the Management Sciences, 1957. — Vol. 5, Iss. 2. — P. 266—288. — 23 p. — ISSN 0030-364X; 1526-5463 — doi:10.1287/OPRE.5.2.266
- .
- ↑ Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин. Применение генетических алгоритмов к решению задач дискретной оптимизации. — 2007. — Нижний Новгород. Архивировано 22 февраля 2016 года.
- ↑ 1 2 3 4 5 С. М. Авдошин, А. А. Савельева. Криптоанализ: современное состояние и перспективы развития . — С. 38. Архивировано 17 марта 2016 года.
- ↑ G. B. Mathews. On the partition of numbers (англ.). — 1897. — P. 486—490. Архивировано 26 мая 2012 года.
- ↑ Kellerer, Pferschy, Pisinger, 2004, p. 3.
- ↑ Kellerer, Pferschy, Pisinger, 2004, p. 9.
- ↑ Р. Карп. Reducibility Among Combinatorial Problems (англ.). — 1972. Архивировано 29 июня 2011 года.
- ↑ Riedhammer et al, 2008, pp. 2436.
- ↑ Шнаер, 2002, p. 19.2.
- ↑ Габидулин, Кшевецкий, Колыбельников, 2011.
- ↑ Бурков, Горгидзе, Ловецкий, 1974, p. 217.
- ↑ 1 2 3 4 Шнаер, 2002, p. 19.1.
- ↑ Kin Ming Lai. Knapsack Cryptosystems: The Past and the Future . — 2001. Архивировано 17 ноября 2012 года.
- ↑ Саломаа, 1995, p. 103.
Литература
- на русском языке
- Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 160—163. — 576 с. — ISBN 978-5-8459-0987-9
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-ое. — М.: «Вильямс», 2006. — С. 456—458. — ISBN 0-07-013151-1.
- Роберт Седжвик. Фундаментальные алгоритмы на 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.
- Бурков В. Н., Горгидзе И. А., Ловецкий С. Е. Прикладные задачи теории графов / под ред. А. Я. Горгидзе — Тбилиси: Вычислительный центр АН СССР, 1974. — 231 с.
- В. Н. Бурков, Д. А. Новиков. Элементы теории графов. — 2001. — С. 28.
- С. Окулов. Программирование в алгоритмах. — 1-е. — Бином. Лаборатория знаний, 2007. — С. 384. — ISBN 5-94774-010-9.
- Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms, and Source Code in C. — 2-ое. — Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4. Архивная копия от 18 декабря 2018 на Wayback Machine
- А. Саломаа. Криптография с открытым ключом = Public-Key Cryptography. — М.: Мир, 1995. — С. 102—150. — ISBN 5–03–001991–X. Архивная копия от 4 марта 2016 на Wayback Machine
- Н. Коблиц. Курс теории чисел в криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 254. — ISBN 5-85484-014-6.
- Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
- Осипян В. О. О системе защиты информации на основе проблемы рюкзака // Известия Томского политехнического университета [Известия ТПУ]. — 2006. — Т. 309, № 2. — С. 209—212.
- на английском языке
- Silvano Martelo, Paolo Toth. Knapsack problems. — Great Britain: Wiley, 1990. — 306 с. — ISBN 0-471-92420-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
- K. Riedhammer, D. Gillick, B. Favre, and D. Hakkani-Tür. Packing the Meeting Summarization Knapsack. — Brisbane Australia: Proc. Interspeech, Brisbane, Australia, 2008.
- 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) (нем.)
Эта статья входит в число хороших статей русскоязычного раздела Википедии. |