Задача о рюкзаке (многомерная)

В предыдущем примере мы рассмотрели классическую одномерную задачу о рюкзаке. В этом примере рассматривается многомерная версия задачи, в которой, помимо ограничения по весу, добавляется ограничение по объему. Это ключевое отличие от классической одномерной модели - остальная структура и логика остаются без изменений.

Постановка задачи

• Имеется 50 предметов. У каждого задана ценность, вес и объем в целочисленных единицах;
• Максимально допустимый вес рюкзака — 850 единиц;
• Объем рюкзака — 700 единиц;
• Необходимо выбрать такие предметы, чтобы их общая ценность была максимальной, при этом суммарный вес и объем не превышали лимиты.

Решение задачи

Далее поэтапно рассмотрим, как реализовать решение этой задачи с использованием библиотеки О₂.

1. Выбор модели

Для подобных задач в О₂ предусмотрена специальная модель — МодельЗадачиРюкзака. Эта модель работает только с целыми числами, как того требует классическая формулировка задачи.

2. Создание объекта модели

Инициализируется многомерная модель задачи о рюкзаке через создание параметров модели с указанием размерности.

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

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

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

3. Ввод данных

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

// Вводим данные
МаксимальныйВес 	= 850; 
МаксимальныйОбъем 	= 700;

// Данные подбираемых предметов
Ценности = О2.Утилиты().МассивЧиселИзСтроки(	
    "360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 
    |670, 892, 600, 38, 48, 147, 78, 256, 63, 17, 
    |120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 
    |514, 28, 87, 73, 78, 15, 26, 78, 210, 36, 
    |85, 189, 274, 43, 33, 10, 19, 389, 276, 312"
);

Веса = О2.Утилиты().МассивЧиселИзСтроки(
    "7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 
    |59, 18, 0, 36, 3, 8, 15, 42, 9, 0, 
    |42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 
    |2, 4, 18, 56, 7, 29, 93, 44, 71, 3, 
    |86, 66, 31, 65, 0, 79, 20, 65, 52, 13"
);

Объемы = О2.Утилиты().МассивЧиселИзСтроки(
    "15, 10, 25, 18, 45, 60, 12, 55, 40, 35, 
    |30, 22, 8, 28, 5, 14, 20, 38, 12, 6, 
    |32, 41, 48, 26, 21, 44, 50, 9, 24, 65, 
    |7, 11, 16, 46, 13, 31, 70, 39, 52, 8, 
    |61, 49, 27, 58, 3, 68, 19, 56, 43, 17"
);

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

Установим максимальный вес и объем рюкзака.

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

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

Для каждого премета создадим элемент модели. Элемент содержит информацию о ценности, весе и объеме предмета.

// Регистрируем элементы модели
Предметы = Новый Массив; 
Для К = 0 По Ценности.ВГраница() Цикл
    Предмет = Модель.Элемент(
        Ценности[К], 
        О2.Утилиты().Массив(Веса[К], Объемы[К]) // <-- массив затрат по каждому измерению модели
    );
    Предметы.Добавить(Предмет);
КонецЦикла;

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

Для получения решения достаточно вызвать метод Решить объекта модели.

// Вызов решателя
Решение = Модель.Решить();

7. Вывод результатов

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

Сообщить("Статус решения: "         + СтатусРешения);
Сообщить("Использовано элементов: " + КоличествоЭлементов);
Сообщить("Суммарная ценность: "     + СуммарнаяЦенность);

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

ОбщийВес 	= 0;
ОбщийОбъем 	= 0;
Для К = 0 По Предметы.ВГраница() Цикл
    Предмет             = Предметы[К];
    ЭлементПрисутствует = Решение.ЭлементПрисутствует(Предмет);
    
    Если ЭлементПрисутствует Тогда
        ОбщийВес 	= ОбщийВес + Веса[К];
        ОбщийОбъем 	= ОбщийОбъем + Объемы[К];
        
        Сообщить(СтрШаблон(
            "  Предмет №%1: ценность=%2, вес=%3, объем=%4", 
            Формат(К + 1, "ЧГ=0"), 
            Ценности[К], 
            Веса[К],
            Объемы[К]
        ));
    КонецЕсли;
КонецЦикла;

Сообщить(СтрШаблон(
    "Общий вес использованных элементов: %1 из %2", 
    ОбщийВес, 
    МаксимальныйВес
));

Сообщить(СтрШаблон(
    "Общий объем использованных элементов: %1 из %2", 
    ОбщийОбъем, 
    МаксимальныйОбъем
));          

Полный код решения задачи

Ниже представлен полный код решения. Вы также можете скачать пример в виде готовой обработки.

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

ПараметрыМодели = МенеджерМоделей.СоздатьПараметрыМодели();

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

Модель = МенеджерМоделей.СоздатьМодель(ПараметрыМодели); 

// Вводим данные
МаксимальныйВес 	= 850; 
МаксимальныйОбъем 	= 700;

// Данные подбираемых предметов
Ценности = О2.Утилиты().МассивЧиселИзСтроки(	
    "360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 
    |670, 892, 600, 38, 48, 147, 78, 256, 63, 17, 
    |120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 
    |514, 28, 87, 73, 78, 15, 26, 78, 210, 36, 
    |85, 189, 274, 43, 33, 10, 19, 389, 276, 312"
);

Веса = О2.Утилиты().МассивЧиселИзСтроки(
    "7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 
    |59, 18, 0, 36, 3, 8, 15, 42, 9, 0, 
    |42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 
    |2, 4, 18, 56, 7, 29, 93, 44, 71, 3, 
    |86, 66, 31, 65, 0, 79, 20, 65, 52, 13"
);

Объемы = О2.Утилиты().МассивЧиселИзСтроки(
    "15, 10, 25, 18, 45, 60, 12, 55, 40, 35, 
    |30, 22, 8, 28, 5, 14, 20, 38, 12, 6, 
    |32, 41, 48, 26, 21, 44, 50, 9, 24, 65, 
    |7, 11, 16, 46, 13, 31, 70, 39, 52, 8, 
    |61, 49, 27, 58, 3, 68, 19, 56, 43, 17"
);

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

// Регистрируем элементы модели
Предметы = Новый Массив; 
Для К = 0 По Ценности.ВГраница() Цикл
    Предмет = Модель.Элемент(
        Ценности[К], 
        О2.Утилиты().Массив(Веса[К], Объемы[К])
    );
    Предметы.Добавить(Предмет);
КонецЦикла;

// Запускаем поиск решения
Решение = Модель.Решить();

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

Сообщить("Статус решения: "         + СтатусРешения);
Сообщить("Использовано элементов: " + КоличествоЭлементов);
Сообщить("Суммарная ценность: "     + СуммарнаяЦенность);

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

ОбщийВес 	= 0;
ОбщийОбъем 	= 0;
Для К = 0 По Предметы.ВГраница() Цикл
    Предмет             = Предметы[К];
    ЭлементПрисутствует = Решение.ЭлементПрисутствует(Предмет);
    
    Если ЭлементПрисутствует Тогда
        ОбщийВес 	= ОбщийВес + Веса[К];
        ОбщийОбъем 	= ОбщийОбъем + Объемы[К];
        
        Сообщить(СтрШаблон(
            "  Предмет №%1: ценность=%2, вес=%3, объем=%4", 
            Формат(К + 1, "ЧГ=0"), 
            Ценности[К], 
            Веса[К],
            Объемы[К]
        ));
    КонецЕсли;
КонецЦикла;

Сообщить(СтрШаблон(
    "Общий вес использованных элементов: %1 из %2", 
    ОбщийВес, 
    МаксимальныйВес
));

Сообщить(СтрШаблон(
    "Общий объем использованных элементов: %1 из %2", 
    ОбщийОбъем, 
    МаксимальныйОбъем
));

  Скачать пример