Задача о рюкзаке
Задача о рюкзаке — это классическая задача оптимизации, в которой нужно отобрать из набора предметов такие, чтобы их суммарная ценность была максимальной, а общий вес (или объём) не превышал заданного ограничения.
Название отражает суть: как наполнить рюкзак наиболее ценными вещами, не перегрузив его.
В практических задачах 1С этот подход может применяться, например, для подбора оптимального ассортимента, формирования отгрузок, выбора поставок или распределения ограниченного бюджета. То есть — в любых ситуациях, где нужно принять решение в условиях ограниченных ресурсов.
В классической задаче о рюкзаке учитываются только интегральные характеристики помещенных в рюкзак предметов. Форма предметов и их геометрическое расположение внутри "рюкзака" не учитываются.
Постановка задачи
- Имеется 50 предметов. У каждого задана ценность и вес в целочисленных единицах;
- Максимально допустимый вес рюкзака — 850 единиц;
- Необходимо выбрать такие предметы, чтобы их общая ценность была максимальной, при этом суммарный вес не превышал максимально допустимый.
Решение задачи
Далее поэтапно рассмотрим, как реализовать решение этой задачи с использованием библиотеки О2.
1. Выбор модели
Для подобных задач в О2 предусмотрена специальная модель — МодельЗадачиРюкзака. Эта модель работает только с целыми числами, как того требует классическая формулировка задачи.
2. Создание модели
Создадим объект модели через менеджер моделей:
// Создание модели задачи рюкзака
Модель = О2
.Модели()
.МодельЗадачиРюкзака()
.СоздатьМодель();
3. Ввод данных
Данные по задаче включают в себя массивы ценностей и весов для всех доступных предметов. Ценности определяют полезность каждого предмета, а веса - затраты места в рюкзаке.
// Вводим данные
МаксимальныйВес = 850;
Ценности = О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"
);
4. Установка ограничений
Установим максимальную вместимость рюкзака.
Модель.Ограничения().Установить(МаксимальныйВес);
5. Добавление элементов
Для каждого премета создадим элемент модели. Элемент содержит информацию о ценности и весе предмета.
// Регистрируем элементы модели
Предметы = Новый Массив;
Для К = 0 По Ценности.ВГраница() Цикл
Предмет = Модель.Элемент(Ценности[К], Веса[К]);
Предметы.Добавить(Предмет);
КонецЦикла;
6. Решение модели
Для получения решения достаточно вызвать метод Решить объекта модели.
// Решаем задачу
Решение = Модель.Решить();
7. Вывод результатов
// Выводим результаты
СтатусРешения = Решение.Статус(); // <-- "Оптимальное" или "Допустимое"
СуммарнаяЦенность = Решение.Ценность(); // <-- значение целевой функции
КоличествоЭлементов = Решение.КоличествоЭлементов(); // <-- количество элементов в рюкзаке
Сообщить("Статус решения: " + СтатусРешения);
Сообщить("Использовано элементов: " + КоличествоЭлементов);
Сообщить("Суммарная ценность: " + СуммарнаяЦенность);
Сообщить("Использованы следующие элементы:" + Символы.ПС);
ОбщийВес = 0;
Для К = 0 По Предметы.Количество() - 1 Цикл
Предмет = Предметы[К];
ЭлементПрисутствует = Решение.ЭлементПрисутствует(Предмет);
Если ЭлементПрисутствует Тогда
ОбщийВес = ОбщийВес + Веса[К];
Сообщить(СтрШаблон(
" Предмет №%1: ценность=%2, вес=%3",
Формат(К + 1, "ЧГ=0"),
Ценности[К],
Веса[К]
));
КонецЕсли;
КонецЦикла;
Сообщить(СтрШаблон(
"Общий вес использованных элементов: %1 из %2",
ОбщийВес,
МаксимальныйВес
));
Полный код решения задачи
Ниже представлен полный код решения. Вы также можете скачать пример в виде готовой обработки.
// Создание модели задачи рюкзака
Модель = О2
.Модели()
.МодельЗадачиРюкзака()
.СоздатьМодель();
// Вводим данные
МаксимальныйВес = 850;
Ценности = О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"
);
// Устанавливаем ограничение
Модель.Ограничения().Установить(МаксимальныйВес);
// Регистрируем элементы модели
Предметы = Новый Массив;
Для К = 0 По Ценности.ВГраница() Цикл
Предмет = Модель.Элемент(Ценности[К], Веса[К]);
Предметы.Добавить(Предмет);
КонецЦикла;
// Решаем задачу
Решение = Модель.Решить();
// Вывод результатов
СтатусРешения = Решение.Статус(); // <-- "Оптимальное" или "Допустимое"
СуммарнаяЦенность = Решение.Ценность(); // <-- значение целевой функции
КоличествоЭлементов = Решение.КоличествоЭлементов(); // <-- количество элементов в рюкзаке
Сообщить("Статус решения: " + СтатусРешения);
Сообщить("Использовано элементов: " + КоличествоЭлементов);
Сообщить("Суммарная ценность: " + СуммарнаяЦенность);
Сообщить("Использованы следующие элементы:" + Символы.ПС);
ОбщийВес = 0;
Для К = 0 По Предметы.Количество() - 1 Цикл
Предмет = Предметы[К];
ЭлементПрисутствует = Решение.ЭлементПрисутствует(Предмет);
Если ЭлементПрисутствует Тогда
ОбщийВес = ОбщийВес + Веса[К];
Сообщить(СтрШаблон(
" Предмет №%1: ценность=%2, вес=%3",
Формат(К + 1, "ЧГ=0"),
Ценности[К],
Веса[К]
));
КонецЕсли;
КонецЦикла;
Сообщить(СтрШаблон(
"Общий вес использованных элементов: %1 из %2",
ОбщийВес,
МаксимальныйВес
));