Модель задачи о рюкзаке

Модель задачи о рюкзаке отбирает из множества доступных элементов подмножество с максимальной суммарной целочисленной ценностью при ограничениях по одному или нескольким ёмкостным ресурсам. По каждому элементу принимается решение «взять или не взять» — копии и дробление одного элемента не поддерживаются (формулировка «0/1»).

В литературе модель известна также как задача о ранце (англ. Knapsack Problem).

Модель реализована как специализированная. На задачах, укладывающихся в её форму, она работает быстрее, чем универсальные линейные модели и модели ограничений. Если задача существенно расширяет классическую формулировку — несколько контейнеров, минимизация количества контейнеров, связи между предметами, дробные количества — применяются упомянутые универсальные модели; см. «Что не покрывается моделью».

Область применения

Алгоритмы решения задачи о рюкзаке применяются там, где требуется принять решение в условиях ограниченных ресурсов: в управлении ассортиментом и запасами в ERP-системах, в складских процедурах класса WMS, в модулях оперативного планирования APS и MES, в задачах S&OP и supply chain optimization, в подсистемах бюджетирования и казначейства.

Типовые сценарии прикладной автоматизации в 1С:Предприятие:

• Отгрузки и комплектация — формирование загрузки одного транспортного средства или одной партии отгрузки по весу и объёму.
• Управление ассортиментом — отбор позиций ассортиментной матрицы под ограниченное место на полке, под доступный товарный кредит или под лимит по обороту.
• Бюджетирование и распределение фонда — отбор инвестиционных инициатив, статей затрат или маркетинговых активностей в рамках выделенного лимита.
• Закупки и поставки — выбор лотов поставщиков под бюджетные ограничения и складские мощности.
• Производственное планирование — отбор партий или работ под ограниченное «окно» производственного цикла, под доступный фонд рабочего времени или под лимит сырья.
• Подбор контента — формирование промо-набора, рассылки или комплекта материалов под ограничение размера, длительности или стоимости.

Типовые задачи

Классическая задача о рюкзаке (0/1 Knapsack)

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

Многомерная задача о рюкзаке (Multidimensional Knapsack, MKP)

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

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

Задачи минимизации

Классическая задача о рюкзаке — это всегда максимизация ценности при ограничении ресурса. Родственные задачи минимизации — например, поиск минимального количества контейнеров, в которые помещаются все предметы (Bin Packing) — этой моделью не покрываются. Они решаются линейной моделью; пример — Оптимизация количества рюкзаков.

Что не покрывается моделью

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

• Несколько контейнеров с разной вместимостью (распределение предметов между N рюкзаками) — реализуется линейной моделью; пример — Задача о нескольких рюкзаках.
• Минимизация количества контейнеров (Bin Packing) — реализуется линейной моделью; пример — Оптимизация количества рюкзаков.
• Геометрическая укладка (раскрой листового материала, упаковка с учётом формы и взаимного расположения предметов) — реализуется моделью ограничений с использованием интервалов и прямоугольников.
• Дробные количества или несколько копий одного предмета — модель работает только в режиме «0/1». Количества предметов как переменные не поддерживаются. Применяется линейная модель.
• Связи и условия между предметами — правила вида «если выбран A, то нельзя B», «не более K элементов из группы», «выбор A требует выбора B». Реализуются моделью ограничений или линейной моделью.

Глоссарий

Термин	Определение
Элемент (предмет)	Объект-кандидат на включение в решение. Несёт ценность и весовые характеристики по каждому измерению модели.
Ценность	Целочисленный вклад элемента в целевую функцию. Суммарная ценность отобранных элементов максимизируется.
Весовая характеристика	Целочисленный «расход ресурса» элементом по одному измерению модели — вес, объём, стоимость, занятая площадь.
Размерность модели	Количество одновременных ёмкостных ограничений. Размерность 1 — классическая (одномерная) задача; размерность 2 и выше — многомерная задача.
Вместимость (ограничение)	Максимально допустимое значение суммарной весовой характеристики по соответствующему измерению. Задаётся отдельным числом для каждого измерения.
Тип решателя	Алгоритм, применяемый для поиска решения. Выбор алгоритма влияет на скорость и точность; см. Выбор алгоритма.
Решение	Подмножество отобранных элементов и значение суммарной ценности. По каждому исходному элементу извлекается признак присутствия в решении.
Статус решения	Признак качества найденного решения: оптимальное (доказана наилучшая суммарная ценность) или допустимое (найдено решение, удовлетворяющее ограничениям, но оптимальность не доказана за отведённое время).

Принцип работы

Решение прикладной задачи моделью задачи о рюкзаке выполняется в следующей последовательности:

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

2. Создание объекта модели. Для одномерной задачи — фасадным вызовом без параметров. Для многомерной — с явным указанием размерности:

   // Одномерная задача
   Модель = О2.Модели().МодельЗадачиРюкзака().СоздатьМодель();
   
   // Многомерная задача
   ПараметрыМодели = О2.Модели().МодельЗадачиРюкзака().СоздатьПараметрыМодели();
   ПараметрыМодели.Размерность = 2;
   
   Модель = О2.Модели().МодельЗадачиРюкзака().СоздатьМодель(ПараметрыМодели);

3. Установка вместимости. Передаётся массив значений по числу измерений модели:

   // Одномерная задача: вместимость по весу — 850
   Модель.Ограничения().Установить(850);
   
   // Многомерная задача: вместимость по весу — 850, по объёму — 700
   Модель.Ограничения().Установить(О2.Утилиты().Массив(850, 700));

4. Регистрация элементов. На каждый элемент-кандидат регистрируется элемент модели с его ценностью и весовыми характеристиками:

   // Одномерная задача: вес = 7
   Модель.Элементы().Добавить(360, 7, "Шкаф");
   
   // Многомерная задача: вес = 7, объём = 12
   Модель.Элементы().Добавить(360, О2.Утилиты().Массив(7, 12), "Шкаф");

5. Запуск поиска решения. В простейшем случае — без параметров. При необходимости задаются тип решателя и лимит времени поиска:

   Решение = Модель.Решить();

6. Обработка решения. Извлекаются статус, суммарная ценность и признаки присутствия отдельных элементов:

   Если Решение.РешениеНайдено() Тогда
       СуммарнаяЦенность = Решение.Ценность();
   
       Для Каждого Элемент Из ЗарегистрированныеЭлементы Цикл
           Если Решение.ЭлементПрисутствует(Элемент) Тогда
               // обработать выбранный элемент
           КонецЕсли;
       КонецЦикла;
   КонецЕсли;

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

Сильные и слабые стороны

Сильные стороны

• Скорость на профильных задачах. Специализированные алгоритмы поиска работают быстрее универсальных моделей на задачах, укладывающихся в форму задачи о рюкзаке.
• Простой API. Полное описание модели сводится к четырём действиям: создать модель, задать вместимость, зарегистрировать элементы, запустить поиск.
• Поддержка многомерных задач. Параметр размерности позволяет учитывать произвольное количество одновременных ёмкостных ограничений без изменения структуры кода.
• Выбор между точными и приближёнными алгоритмами. Доступные типы решателей различаются соотношением «скорость — гарантии оптимальности». Это позволяет адаптировать модель к размеру конкретной задачи.

Слабые стороны и пределы применимости

• Только целочисленные значения. Ценности и веса должны быть целыми. Дробные значения моделируются масштабированием — умножением на 10ⁿ.
• Только формулировка «0/1». По каждому элементу принимается бинарное решение «взять или не взять». Несколько копий одного элемента (bounded и unbounded knapsack) и дробные количества средствами модели не выражаются.
• Один контейнер. Модель описывает ровно один рюкзак с заданными ограничениями. Распределение элементов между несколькими контейнерами требует линейной модели.
• Нет связей между элементами. Условные правила выбора («если выбран A, то нельзя B»; «не более K из группы») средствами модели не выражаются. Реализуются через модель ограничений или линейную модель.

Выбор алгоритма

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

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

Доступные типы решателей и характерные ситуации применения:

Тип решателя	Когда применять
DP	Точный метод динамического программирования. Эффективен на одномерных задачах с относительно небольшими значениями вместимости и ценностей. Гарантирует оптимальное решение.
Items64	Точный метод полного перебора, оптимизированный для задач с количеством элементов не более 64. Работает быстро, если количество элементов гарантированно укладывается в указанный предел.
BF	Точный метод полного перебора без ограничений на количество элементов. Применяется на очень маленьких задачах или для отладки и контрольной проверки решения.
CBC, SCIP	Методы линейной целочисленной оптимизации. Применяются на многомерных задачах, а также на крупных одномерных, где динамическое программирование неэффективно.
SAT	Метод, основанный на программировании в ограничениях. Подходит для задач со сложной комбинаторной структурой. Допускает ограничение времени поиска с возвратом текущего лучшего решения.

Полный перечень и сигнатуры — в API-разделе: ТипыРешателей.

Примеры

Используют модель задачи о рюкзаке

• Решение классической задачи о рюкзаке
• Решение многомерной задачи о рюкзаке

Выходят за границы модели — реализованы линейной моделью

• Задача о нескольких рюкзаках — распределение предметов между несколькими контейнерами с разной вместимостью.
• Оптимизация количества рюкзаков (Bin Packing) — минимизация количества контейнеров, достаточного для размещения всех предметов.

Программный интерфейс

Полное описание методов модели задачи о рюкзаке приведено в разделе Программный интерфейс — Задача о рюкзаке.