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

Задача о рюкзаке (англ. Knapsack Problem) — это классическая проблема выбора оптимального набора предметов с ограниченной вместимостью. Название связано с наглядной аналогией: как уместить в рюкзак наиболее ценные вещи при ограниченном объёме.

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

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

Создание модели

Одномерная модель

Создание через менеджер моделей:

Модель = О2
    .Модели()
    .МодельЗадачиРюкзака()
    .СоздатьМодель();

Создание через менеджер библиотеки:

Модель = О2.СоздатьМодель(
    О2.ТипыМоделей().МодельЗадачиРюкзака()
);

Многомерная модель

Создание через менеджер моделей:

МенеджерМоделей = О2
    .Модели()
    .МодельЗадачиРюкзака();

ПараметрыМодели = МенеджерМоделей.СоздатьПараметрыМодели();
ПараметрыМодели.Размерность = 2; // <-- указываем размерность модели

Модель = МенеджерМоделей.СоздатьМодель(ПараметрыМодели);  // <-- указываем параметры при создании

Создание через менеджер библиотеки:

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

ПараметрыМодели.Размерность = 2;

Модель = О2.СоздатьМодель(
    О2.ТипыМоделей().МодельЗадачиРюкзака(),
    ПараметрыМодели
);  

Установка ограничений

Одномерная модель

МаксимальныйВес = 100;

Модель.Ограничения().Установить(МаксимальныйВес);

Многомерная модель

МаксимальныйВес     = 100;  // <-- ограничение по первому измерению
МаксимальныйОбъем   = 1000; // <-- ограничение по второму измерению

Модель.Ограничения().Установить(
    О2.Утилиты().Массив(МаксимальныйВес, МаксимальныйОбъем)     // <-- массив из двух значений
);

Для получения текущих установленных ограничений:

Ограничения = Модель.Ограничения().Получить(); // <-- всегда массив чисел

Добавление элементов

Одномерная модель

Имя         = "Шкаф";   // <-- имя элемента (опционально)
Ценность    = 10;       // <-- ценность элемента
Вес         = 35;

Элемент = Модель.Элемент(Ценность, Вес, Имя);

Многомерная модель

Имя         = "Шкаф";   // <-- имя элемента (опционально)
Ценность    = 10;       // <-- ценность элемента
Вес         = 35;       // <-- весовое значение по первому измерению
Объем       = 80;       // <-- весовое значение по второму измерению

Элемент = Модель.Элемент(
    Ценность, 
    О2.Утилиты().Массив(Вес, Объем),    // <-- весовые значения по обоим измерениям
    Имя
);

Решение модели

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

НастройкиРешателя = О2.СоздатьНастройкиРешателя();
НастройкиРешателя.ТипРешателя = О2
    .Модели()
    .МодельЗадачиРюкзака()
    .ТипыРешателей()
    .DP();      // <-- метод динамического программирования

ПараметрыРешения = О2.СоздатьПараметрыРешения();
ПараметрыРешения.НастройкиРешателя = НастройкиРешателя;

Решение = Модель.Решить(ПараметрыРешения);

Обработка результата

СтатусРешения       = Решение.Статус();                 // <-- "Оптимальное" или "Допустимое"
СуммарнаяЦенность   = Решение.Ценность();               // <-- значение целевой функции
КоличествоЭлементов = Решение.КоличествоЭлементов();    // <-- количество элементов, поместившихся в рюкзак

Сообщить(
    СтрШаблон("Использовано элементов: %1. Суммарная ценность: %2.",  КоличествоЭлементов, СуммарнаяЦенность)
);

Сообщить("Использованы следующие элементы:");

Для Каждого Элемент Из Элементы Цикл        // <-- Элементы - это массив элементов, добавленных в модель
    ЭлементПрисутсвует = Решение.ЭлементПрисутсвует(Элемент);

    Если ЭлементПрисутсвует Тогда
        Сообщить(Элемент.Имя);
    КонецЕсли;
КонецЦикла;