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

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

¶История

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

В 1970-х годах задача о рюкзаке стала объектом активного изучения в связи с развитием теории NP-полноты. В 1972 году Ричард Карп показал, что задача о рюкзаке (в варианте с целыми весами) является NP-полной, что означает отсутствие известного полиномиального алгоритма для её точного решения. Это стимулировало разработку приближённых алгоритмов и методов эвристики.

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

¶Формальная постановка

Пусть имеется n предметов, каждый из которых характеризуется весом w_i (целое или вещественное число) и стоимостью v_i (целое или вещественное число). Вместимость рюкзака задана числом W (максимальный допустимый вес). Необходимо найти подмножество предметов S ⊆ {1,2,…,n}, такое что:

• ∑(i∈S) w_i ≤ W
• ∑(i∈S) v_i → max

Переменные решения x_i ∈ {0,1} указывают, включён ли предмет i в рюкзак. Тогда задача формулируется как:

Максимизировать ∑(i=1..n) v_i · x_i при условии ∑(i=1..n) w_i · x_i ≤ W, x_i ∈ {0,1}.

¶Классификация

Задача о рюкзаке имеет несколько разновидностей, различающихся по условиям на предметы и целевую функцию:

¶По типу предметов

• 0-1 рюкзак (бинарный) — каждый предмет можно взять не более одного раза (классическая постановка).
• Ограниченный рюкзак (bounded) — для каждого предмета задано максимальное количество копий, которые можно взять.
• Неограниченный рюкзак (unbounded) — каждый предмет можно брать любое количество раз.
• Дробный рюкзак (fractional) — предметы можно делить, задача решается жадным алгоритмом за полиномиальное время и не является NP-трудной.

¶По характеру весов и стоимостей

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

¶По целевой функции

• Максимизация стоимости — стандартная постановка.
• Минимизация веса при заданной минимальной стоимости (обратная задача).
• Многокритериальный рюкзак — несколько целевых функций (например, стоимость и надёжность).

¶Методы решения

¶Точные алгоритмы

• Динамическое программирование — для целочисленных весов строится таблица размером (n+1)×(W+1), где ячейка [i][w] хранит максимальную стоимость для первых i предметов при весе не более w. Временная сложность — O(n·W), что является псевдополиномиальным.
• Метод ветвей и границ — рекурсивный перебор с отсечением заведомо неоптимальных ветвей. Эффективен для небольших n (до 50–100).
• Метод Гомори — для целочисленного линейного программирования, применим к задаче о рюкзаке.

¶Приближённые алгоритмы

• Жадный алгоритм — сортировка предметов по убыванию отношения стоимости к весу (v_i/w_i) и последовательное добавление, пока позволяет вместимость. Не гарантирует оптимальность, но даёт приближение с коэффициентом 1/2 для 0-1 рюкзака.
• Схема полиномиальной аппроксимации (FPTAS) — для любого ε > 0 находит решение с относительной ошибкой не более ε за время O(n·1/ε). Пример — алгоритм Ибарры и Кима (1975).

¶Эвристические методы

• Генетические алгоритмы — популяция решений, скрещивание и мутация.
• Муравьиные алгоритмы — имитация поведения муравьёв при поиске пути.
• Имитация отжига — вероятностный поиск с уменьшением температуры.

¶Применение

• Логистика и транспорт — загрузка грузовиков, контейнеров, самолётов с учётом веса и объёма.
• Финансы — портфельная оптимизация (выбор акций с ограничением на бюджет).
• Криптография — ранцевые криптосистемы (например, Меркля-Хеллмана), хотя большинство из них взломаны.
• Производство — раскрой материалов (например, резка листов металла или ткани).
• Управление проектами — распределение ресурсов между задачами с ограничением бюджета.
• Машинное обучение — выбор признаков (feature selection) с ограничением на количество признаков.

¶Пример

Дано: 3 предмета с весами (2, 3, 4) и стоимостями (3, 4, 5), вместимость рюкзака W = 5.

• Возможные подмножества:
• {1}: вес 2, стоимость 3
• {2}: вес 3, стоимость 4
• {3}: вес 4, стоимость 5
• {1,2}: вес 5, стоимость 7 (оптимальное)
• {1,3}: вес 6 > W — недопустимо
• {2,3}: вес 7 > W — недопустимо

Оптимальное решение — взять предметы 1 и 2, общая стоимость 7.

¶Интересные факты

• Задача о рюкзаке является одной из 21 NP-полной задачи, перечисленных Ричардом Карпом в 1972 году.
• В 1998 году был предложен алгоритм, решающий задачу о рюкзаке с n до 10 000 и W до 1 000 000 за приемлемое время с использованием динамического программирования и оптимизации памяти.
• Существует вариант задачи, называемый «задача о рюкзаке с ограничением на количество предметов», который используется в теории кодирования.
• В 2010 году группа исследователей из MIT показала, что для случайных данных задача о рюкзаке может быть решена за полиномиальное время с высокой вероятностью.

¶Критика и ограничения

• NP-трудность делает точное решение невозможным для больших размеров (n > 1000) за разумное время без специальных структур данных.
• Алгоритмы динамического программирования требуют памяти O(n·W), что при больших W (например, 10^9) становится неприемлемым.
• Приближённые алгоритмы дают гарантии только для худшего случая, на практике их точность может быть ниже ожидаемой.
• В реальных задачах часто присутствуют дополнительные ограничения (многомерность, временные окна, зависимости между предметами), что усложняет модель.

¶Источники

• Данциг, Дж. (1957). «Discrete-Variable Extremum Problems». Operations Research.
• Карп, Р. (1972). «Reducibility Among Combinatorial Problems». Complexity of Computer Computations.
• Меркль, Р., Хеллман, М. (1978). «Hiding Information and Signatures in Trapdoor Knapsacks». IEEE Transactions on Information Theory.
• Шамир, А. (1982). «A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem». Advances in Cryptology.
• Ибарра, О., Ким, Ч. (1975). «Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems». Journal of the ACM.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2009). «Алгоритмы: построение и анализ».