Задача об укладке рюкзака

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

История

Задача об укладке рюкзака впервые была формально описана в 1957 году американским математиком Джорджем Данцигом, хотя её ранние версии встречались в работах экономистов и математиков начала XX века. Данциг, известный как создатель симплекс-метода, сформулировал задачу как модель для оптимизации загрузки транспортных средств. В 1972 году Ричард Карп включил задачу о рюкзаке в список 21 NP-полной задачи, что подтвердило её фундаментальную сложность. С развитием вычислительной техники в 1980-х годах задача стала широко применяться в криптографии, логистике и финансах.

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

Пусть имеется рюкзак вместимостью \( W \) (целое положительное число) и \( n \) предметов. Каждый предмет \( i \) характеризуется весом \( w_i \) и стоимостью \( c_i \) (целые числа). Необходимо выбрать подмножество предметов \( S \subseteq \{1, 2, \dots, n\} \) такое, что:

\[ \sum_{i \in S} w_i \leq W, \quad \sum_{i \in S} c_i \to \max \]

Переменные решения: \( x_i \in \{0, 1\} \), где \( x_i = 1 \), если предмет включён, и \( 0 \) в противном случае. Целевая функция: \( \max \sum_{i=1}^n c_i x_i \) при ограничении \( \sum_{i=1}^n w_i x_i \leq W \).

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

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

0-1 рюкзак (0-1 knapsack)

Каждый предмет можно взять не более одного раза. Это наиболее распространённая версия, рассматриваемая в классической постановке.

Ограниченный рюкзак (bounded knapsack)

Для каждого предмета задано максимальное количество копий \( k_i \), которые можно взять. Сводится к 0-1 рюкзаку путём разбиения предмета на \( k_i \) единичных экземпляров.

Неограниченный рюкзак (unbounded knapsack)

Предметы можно брать в любом количестве (неограниченное число копий). Решается модифицированным алгоритмом динамического программирования.

Дробный рюкзак (fractional knapsack)

Предметы можно делить на части, и стоимость пропорциональна взятой части. Решается жадным алгоритмом за полиномиальное время, в отличие от других вариантов.

Многомерный рюкзак (multidimensional knapsack)

Учитывается несколько ограничений (например, вес и объём). Каждый предмет имеет несколько параметров, и все ограничения должны быть соблюдены.

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

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

Динамическое программирование

Классический метод для 0-1 рюкзака с целыми весами. Строится таблица \( dp[i][w] \) — максимальная стоимость для первых \( i \) предметов при весе не более \( w \). Рекуррентное соотношение:

\[ dp[i][w] = \max(dp[i-1][w], dp[i-1][w - w_i] + c_i) \]

Временная сложность: \( O(nW) \), что псевдополиномиально (зависит от значения \( W \), а не от его битовой длины). Для неограниченного рюкзака используется одномерная версия с проходом по весу в прямом порядке.

Жадные алгоритмы

Для дробного рюкзака жадный алгоритм, сортирующий предметы по убыванию удельной стоимости \( c_i / w_i \), даёт оптимальное решение. Для 0-1 рюкзака жадный подход не гарантирует оптимума, но может использоваться как эвристика.

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

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

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

• FPTAS (Fully Polynomial-Time Approximation Scheme): для любого \( \varepsilon > 0 \) находит решение со стоимостью не менее \( (1 - \varepsilon) \) от оптимальной за время \( O(n \log(1/\varepsilon) + n / \varepsilon^2) \). Основан на масштабировании стоимостей.
• Жадные эвристики: сортировка по удельной стоимости, затем последовательное добавление предметов.

Генетические алгоритмы и имитация отжига

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

Применение

Задача об укладке рюкзака имеет широкое практическое применение в различных областях:

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

Пример

Рассмотрим рюкзак вместимостью \( W = 10 \) и три предмета:

Оптимальное решение: взять предметы A и C (вес 8, стоимость 15). Предмет B даёт вес 4 и стоимость 7, но в комбинации с A превышает вместимость. Жадный алгоритм по удельной стоимости (A: 2, B: 1.75, C: 1.67) выберет A (вес 5, стоимость 10), затем B (вес 9, стоимость 17) — но это превышает лимит, поэтому жадный алгоритм даст только A (стоимость 10), что неоптимально.

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

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

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

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

Источники

• Dantzig, G. B. (1957). "Discrete-Variable Extremum Problems". Operations Research.
• Karp, R. M. (1972). "Reducibility Among Combinatorial Problems". In: Miller, R. E., Thatcher, J. W. (eds.) Complexity of Computer Computations.
• Martello, S., Toth, P. (1990). "Knapsack Problems: Algorithms and Computer Implementations". Wiley.
• Kellerer, H., Pferschy, U., Pisinger, D. (2004). "Knapsack Problems". Springer.