В практической деятельности программиста 1С нередко возникает задача, когда необходимо автоматически заполнить табличную часть документа товарами со склада так, чтобы их суммарная стоимость максимально точно соответствовала заданной сумме. Такая потребность часто встречается при автоматическом формировании подарочных наборов, распределении бонусов, составлении спецификаций под фиксированный бюджет или при оформлении корректирующих документов для выравнивания учета.
С точки зрения математики и теории алгоритмов, эта задача классифицируется как "Задача о суммах подмножеств" (частный случай классической "Задачи о ранце" / Knapsack Problem). Это NP-полная задача, для которой не существует быстрого точного решения методом простого перебора при большом количестве позиций. Попытка решить её "в лоб" с помощью вложенных циклов может привести к зависанию сеанса пользователя или чрезмерной нагрузке на сервер СУБД.
В рамках этой статьи мы подробно разберем, какие критические ошибки совершают разработчики при попытке реализовать подобный подбор, как правильно оптимизировать запросы к остаткам и какие алгоритмы лучше всего использовать для быстрого и точного расчета.
Рассмотрим по шагам код, который часто предлагают начинающие разработчики (аналогичный представленному в начале обсуждения). В нем можно выделить сразу несколько грубых архитектурных ошибок:
Запрос, которые обращаются к одной и той же виртуальной таблице остатков РегистрНакопления.ПартииТоваровНаСкладах.Остатки. Каждый такой запрос — это тяжелое обращение к СУБД, требующее времени на компиляцию плана запроса и получение данных.КоличествоОстаток > 0) выполняется в секции ГДЕ, а не в параметрах виртуальной таблицы. Это заставляет СУБД сначала прочитать абсолютно все записи регистра остатков, построить временную таблицу в памяти и только потом отфильтровать ее. При объеме справочника номенклатуры в сотни тысяч или миллионы позиций это гарантированно приведет к критическому падению производительности.Для каждого К Из Рез4 -> Для каждого С Из Рез2) имеют экспоненциальную сложность O(N^2) или даже O(N^3). Если в выборку попадет хотя бы 1000 товаров, количество итераций перебора составит миллионы, что приведет к зависанию процесса rphost.(НеобходимаяСумма - С.Цена*Н)/НеобходимаяСумма могут накапливать погрешность из-за особенностей представления дробных чисел на уровне платформы и СУБД.Выясним причину, как оптимизировать этот процесс и сделать решение пригодным для реальных баз данных с миллионными оборотами.
Для начала напишем один-единственный и максимально производительный запрос, который соберет все необходимые данные о доступных товарах и их ценах. Мы сразу отсечем все лишние позиции на уровне СУБД и проиндексируем результаты для последующей быстрой обработки в коде 1С.
// Подготовим запрос для получения цен и остатков в один проход
ЗапросОстатков = Новый Запрос;
ЗапросОстатков.Текст =
"ВЫБРАТЬ
| ПартииТоваров.Номенклатура КАК Номенклатура,
| ПартииТоваров.КоличествоОстаток КАК КоличествоОстаток,
| ПартииТоваров.СтоимостьОстаток КАК СтоимостьОстаток,
| ВЫБОР
| КОГДА ПартииТоваров.КоличествоОстаток = 0 ТОГДА 0
| ИНАЧЕ ВЫРАЗИТЬ(ПартииТоваров.СтоимостьОстаток / ПартииТоваров.КоличествоОстаток КАК ЧИСЛО(15, 2))
| КОНЕЦ КАК Цена
|ПОМЕСТИТЬ ВТ_ОстаткиСЦенеми
|ИЗ
| РегистрНакопления.ПартииТоваровНаСкладах.Остатки(, КоличествоОстаток > 0) КАК ПартииТоваров
|;
|
|////////////////////////////////////////////////////////////////////////////////
|ВЫБРАТЬ
| ВТ.Номенклатура КАК Номенклатура,
| ВТ.КоличествоОстаток КАК КоличествоОстаток,
| ВТ.Цена КАК Цена
|ИЗ
| ВТ_ОстаткиСЦенеми КАК ВТ
|ГДЕ
| ВТ.Цена > 0
| И ВТ.Цена <= &МаксимальноДопустимаяЦена
|
|УПОРЯДОЧИТЬ ПО
| Цена УБЫВ
|ИНДЕКСИРОВАТЬ ПО
| Цена";
ЗапросОстатков.УстановитьПараметр("МаксимальноДопустимаяЦена", НеобходимаяСумма);
РезультатЗапроса = ЗапросОстатков.Выполнить();
ТаблицаТоваров = РезультатЗапроса.Выгрузить();
Проанализируем преимущества этого запроса:
КоличествоОстаток > 0 передан в качестве параметра виртуальной таблицы остатков. Это позволяет платформе 1С передать СУБД оптимальный SQL-запрос, выбирающий только нужные записи.ВЫРАЗИТЬ гарантирует, что рассчитанная цена будет приведена к точному типу с двумя знаками после запятой, что исключает ошибки округления при делении стоимости на количество.ИНДЕКСИРОВАТЬ ПО Цена во временной таблице ускоряет отбор и сортировку данных.Когда данные быстро получены в память, перед разработчиком встает задача эффективной сборки комбинации товаров. Рассмотрим три основных подхода к решении задачи.
Это самый популярный метод в бизнес-приложениях. Его суть заключается в том, что мы сортируем товары по убыванию цены и пытаемся взять как можно больше самого дорогого товара, затем переходим к более дешевому, пока не наберем нужную сумму.
Рассмотрим пример программной реализации жадного алгоритма в 1С:
Функция ПодобратьТоварыЖаднымМетодом(ТаблицаТоваров, ЦелеваяСумма)
// Создаем таблицу для результата
ТаблицаРезультата = Новый ТаблицаЗначений;
ТаблицаРезультата.Колонки.Добавить("Номенклатура");
ТаблицаРезультата.Колонки.Добавить("Количество");
ТаблицаРезультата.Колонки.Добавить("Цена");
ТаблицаРезультата.Колонки.Добавить("Сумма");
ОставшаясяСумма = ЦелеваяСумма;
// Перебираем товары, отсортированные по убыванию цены
Для Каждого СтрокаТовара Из ТаблицаТоваров Цикл
Если ОставшаясяСумма <= 0 Тогда
Прервать;
КонецЕсли;
// Определяем, сколько штук мы можем себе позволить по деньгам
ДоступноПоДЕНЬГАМ = Цел(ОставшаясяСумма / СтрокаТовара.Цена);
// Берем минимум между тем, что можем купить, и тем, что физически есть на складе
КоличествоДляВзятия = Мин(ДоступноПоДЕНЬГАМ, СтрокаТовара.КоличествоОстаток);
Если КоличествоДляВзятия > 0 Тогда
СтрокаРез = ТаблицаРезультата.Добавить();
СтрокаРез.Номенклатура = СтрокаТовара.Номенклатура;
СтрокаРез.Количество = КоличествоДляВзятия;
СтрокаРез.Цена = СтрокаТовара.Цена;
СтрокаРез.Сумма = КоличествоДляВзятия * СтрокаТовара.Цена;
ОставшаясяСумма = ОставшаясяСумма - СтрокаРез.Сумма;
КонецЕсли;
КонецЦикла;
Возврат ТаблицаРезультата;
КонецФункции
Преимущества: Работает мгновенно (сложность O(N)), не нагружает память сервера и процессор.
Недостатки: Может не найти точную сумму, если останутся нераспределенные остатки (например, целевая сумма 100, алгоритм взял товар за 90 рублей, осталась сумма 10, а на складе самый дешевый товар стоит 15 рублей. В итоге подбор завершится с недобором в 10 рублей, хотя на складе могли быть два товара по 50 рублей).
Если жадный алгоритм выдал результат с слишком большим отклонением от целевой суммы, отличным решением является запуск контролируемого случайного поиска. Мы делаем фиксированное количество попыток собрать случайный набор товаров и запоминаем ту комбинацию, которая показала наименьшее отклонение от цели.
Разберем по шагам реализацию этого метода:
Функция ПодобратьТоварыМетодомМонтеКарло(ТаблицаТоваров, ЦелеваяСумма, МаксПопыток = 1000)
Генератор = Новый ГенераторСлучайныхЧисел;
ЛучшееОтклонение = ЦелеваяСумма; // Худший вариант — набрали 0 руб.
ЛучшийНабор = Неопределено;
КоличествоСтрок = ТаблицаТоваров.Количество();
Если КоличествоСтрок = 0 Тогда
Возврат Неопределено;
КонецЕсли;
Для Итерация = 1 По МаксПопыток Цикл
ВременныйНабор = Новый Соответствие; // Ключ: Номенклатура, Значение: Структура(Количество, Цена)
ТекущаяСуммаНабора = 0;
// Делаем случайные шаги добавления товаров, пока не превысим сумму
ПопытокДобавления = 0;
Пока ТекущаяСуммаНабора < ЦелеваяСумма И ПопытокДобавления < 100 Цикл
// Выбираем случайную строку номенклатуры
ИндексСлучайный = Генератор.СлучайноеЧисло(0, КоличествоСтрок - 1);
ВыбранныйТовар = ТаблицаТоваров[ИндексСлучайный];
// Проверим, не исчерпан ли лимит этого товара
ТекущееКоличествоВНаборе = 0;
НайденныйТовар = ВременныйНабор.Получить(ВыбранныйТовар.Номенклатура);
Если НайденныйТовар <> Неопределено Тогда
ТекущееКоличествоВНаборе = НайденныйТовар.Количество;
КонецЕсли;
Если ТекущееКоличествоВНаборе < ВыбранныйТовар.КоличествоОстаток Тогда
// Проверяем, не перешагнем ли мы лимит по сумме слишком сильно
Если ТекущаяСуммаНабора + ВыбранныйТовар.Цена <= ЦелеваяСумма Тогда
Если НайденныйТовар = Неопределено Тогда
ВременныйНабор.Вставить(ВыбранныйТовар.Номенклатура, Новый Структура("Количество, Цена", 1, ВыбранныйТовар.Цена));
ИНАЧЕ
НайденныйТовар.Количество = НайденныйТовар.Количество + 1;
КонецЕсли;
ТекущаяСуммаНабора = ТекущаяСуммаНабора + ВыбранныйТовар.Цена;
ПопытокДобавления = 0; // Сбрасываем счетчик неудачных попыток
Иначе
ПопытокДобавления = ПопытокДобавления + 1;
КонецЕсли;
Иначе
ПопытокДобавления = ПопытокДобавления + 1;
КонецЕсли;
КонецЦикла;
// Оцениваем отклонение текущего набора от идеала
ТекущееОтклонение = ЦелеваяСумма - ТекущаяСуммаНабора;
Если ТекущееОтклонение >= 0 И ТекущееОтклонение < ЛучшееОтклонение Тогда
ЛучшееОтклонение = ТекущееОтклонение;
ЛучшийНабор = ВременныйНабор;
// Если нашли идеальное соответствие — прекращаем поиск досрочно
Если ЛучшееОтклонение = 0 Тогда
Прервать;
КонецЕсли;
КонецЕсли;
КонецЦикла;
// Преобразуем структуру лучшего набора в ТаблицуЗначений для возврата
ТаблицаРезультата = Новый ТаблицаЗначений;
ТаблицаРезультата.Колонки.Добавить("Номенклатура");
ТаблицаРезультата.Колонки.Добавить("Количество");
ТаблицаРезультата.Колонки.Добавить("Цена");
ТаблицаРезультата.Колонки.Добавить("Сумма");
Если ЛучшийНабор <> Неопределено Тогда
Для Каждого Элемент Из ЛучшийНабор Цикл
СтрокаРез = ТаблицаРезультата.Добавить();
СтрокаРез.Номенклатура = Элемент.Ключ;
СтрокаРез.Количество = Элемент.Значение.Количество;
СтрокаРез.Цена = Элемент.Значение.Price;
СтрокаРез.Сумма = Элемент.Значение.Количество * Элемент.Значение.Цена;
КонецЦикла;
КонецЕсли;
Возврат ТаблицаРезультата;
КонецФункции
Метод Монте-Карло гарантирует высокую скорость выполнения, поскольку количество итераций жестко ограничено числом в параметре МаксПопыток. При этом вероятность подобрать комбинацию с нулевым или минимальным отклонением (до копеек) крайне высока на реальных данных за счет разнообразия цен товаров.
Это классический математический подход, гарантирующий нахождение абсолютно точной суммы, если она теоретически собирается из имеющегося набора цен. Однако этот метод требует перевода цен в целые числа (например, путем умножения на 100 для избавления от копеек) и создания больших массивов в памяти.
Для оптимизации памяти в 1С при динамическом программировании рекомендуется:
Число без дробной части.Чтобы разработанный вами функционал подбора работал стабильно в любой информационной базе, придерживайтесь следующих правил безопасности:
Если СчетчикИтераций > 10000 Тогда ВызватьИсключение "Превышен лимит времени расчета"; КонецЕсли;.Использование связки из оптимального одиночного запроса с индексацией и жадного алгоритма с последующей доработкой методом Монте-Карло позволяет решать задачу подбора на сумму мгновенно и с высочайшей точностью даже на базах с миллионами номенклатурных позиций.