В процессе разработки в среде 1С программисты часто сталкиваются с задачей распределения данных. Типичный пример: имеется ТаблицаЗначений со списком товаров, их количеством и суммами, и необходимо разделить эту таблицу на $k$ отдельных таблиц (или документов) так, чтобы общая сумма каждой из них была приблизительно одинаковой. Такая задача актуальна при подготовке документов для логистики, разделении крупных заказов для разных курьеров или оптимизации лимитов на отгрузку.
На первый взгляд задача кажется простой, но попытки решить ее "в лоб" (последовательно наполняя каждую таблицу до достижения средней суммы) приводят к огромной погрешности. В этой статье мы подробно проанализируем причины этой погрешности, разберем математическую суть проблемы и рассмотрим два эффективных алгоритма решения на встроенном языке 1С с готовыми примерами кода.
Рассмотрим стандартный подход, который часто пытаются применить начинающие разработчики. Вычисляется средняя сумма одного документа как общая сумма всех товаров, деленная на требуемое количество документов. Затем запускается цикл по исходной таблице значений, и строки последовательно переносятся в первый документ до тех пор, пока его сумма не приблизится к средней. После этого алгоритм переходит ко второму документу, к третьему и так далее.
Проанализируем, почему этот алгоритм дает плохой результат:
Выясним, как решить эту задачу правильно с точки зрения теории алгоритмов и практики программирования в 1С.
В математике и теории алгоритмов описанная проблема известна как задача о мульти-разбиении чисел (Multiway Number Partitioning). Она относится к классу NP-полных задач комбинаторной оптимизации. Это означает, что найти абсолютно точное (идеальное) распределение за приемлемое время путем простого перебора всех вариантов невозможно, особенно если в исходной таблице сотни или тысячи строк.
Однако для практических задач высокая точность "копейка в копейку" обычно не требуется — достаточно минимизировать погрешность (среднеквадратическое отклонение сумм полученных документов от средней величины). Для этого используются эффективные эвристические методы.
Наиболее популярный и простой в реализации метод — это алгоритм LPT (Longest Processing Time first), который также называют жадным алгоритмом с предварительной сортировкой по убыванию. Математически доказано, что погрешность данного метода на практике составляет доли процента, а сам алгоритм выполняется мгновенно.
Рассмотрим два варианта решения этой задачи на платформе 1С: параллельное распределение методом LPT (рекомендуемый способ) и последовательное распределение с дроблением штучного товара.
Суть этого подхода заключается в том, что мы заполняем все целевые таблицы **параллельно**, а не последовательно. Выберем этот метод как основной. Проанализируем алгоритм по шагам:
Сумма в направлении убывания. Это ключевой момент: сначала мы должны распределить самые дорогие товары, так как их сложнее всего "пристроить" в конце, а более дешевые товары будут играть роль "наполнителя" для выравнивания сумм на финальных шагах.Посмотрим на пример реализации данного алгоритма на встроенном языке 1С:
// Функция распределяет исходную ТЗ на указанное количество таблиц
// Параметры:
// ИсходнаяТЗ - ТаблицаЗначений, содержащая колонки Товар, Количество, Сумма
// КоличествоГрупп - Число, на сколько частей нужно разбить
// Возвращает: Массив, содержащий новые ТаблицыЗначений с распределенными данными
Функция РаспределитьТаблицуПоСуммеЖаднымМетодом(ИсходнаяТЗ, КоличествоГрупп) Экспорт
// 1. Подготавливаем массив результирующих таблиц
МассивРезультатов = Новый Массив;
МассивСумм = Новый Массив; // Хранилище текущих сумм для быстрого доступа
Для Счетчик = 1 По КоличествоГрупп Цикл
НоваяТЗ = ИсходнаяТЗ.СкопироватьКолонки();
МассивРезультатов.Добавить(НоваяТЗ);
МассивСумм.Добавить(0); // Изначально сумма каждой таблицы равна 0
КонецЦикла;
// 2. Копируем исходную таблицу, чтобы не испортить исходные данные, и сортируем по убыванию суммы
ТЗСортированная = ИсходнаяТЗ.Скопировать();
ТЗСортированная.Сортировать("Сумма Убыв");
// 3. Распределяем строки по таблицам с минимальной текущей суммой
Для Каждого СтрокаИсточника Из ТЗСортированная Цикл
// Находим индекс таблицы с минимальной накопленной суммой
ИндексМинимума = 0;
МинимальнаяСумма = МассивСумм[0];
Для Индекс = 1 По КоличествоГрупп - 1 Цикл
Если МассивСумм[Индекс] < МинимальнаяСумма Тогда
МинимальнаяСумма = МассивСумм[Индекс];
ИндексМинимума = Индекс;
КонецЕсли;
КонецЦикла;
// Добавляем строку в выбранную таблицу
ПолучательТЗ = МассивРезультатов[ИндексМинимума];
НоваяСтрока = ПолучательТЗ.Добавить;
ЗаполнитьЗначенияСвойств(НоваяСтрока, СтрокаИсточника);
// Обновляем накопленную сумму для этой таблицы
МассивСумм[ИндексМинимума] = МассивСумм[ИндексМинимума] + СтрокаИсточника.Сумма;
КонецЦикла;
Возврат МассивРезультатов;
КонецФункции
Преимущества этого решения: Алгоритм чрезвычайно прост, не требует сложных математических вычислений, не делит штучный товар на части (что часто запрещено бизнес-логикой) и работает очень быстро (за один проход по таблице). Погрешность распределения при количестве строк более 50 обычно стремится к нулю.
Бывают ситуации, когда бизнес-требования обязывают заполнять документы строго последовательно, а для выравнивания сумм разрешается дробить количество товара в строке (например, если товар весовой или штучный, но его много в одной строке). В этом случае нам необходимо аккуратно рассчитывать остатки, чтобы не потерять копейки и единицы количества.
Проанализируем ситуацию, когда мы обходим таблицу и понимаем, что добавление текущей строки целиком превысит среднюю целевую сумму документа. Нам нужно рассчитать, какое максимальное количество товара из этой строки мы можем забрать в текущий документ, а остаток количества и суммы оставить в исходной таблице для последующих документов.
Разберем по шагам реализацию такого алгоритма, исправляя типичные ошибки с пересчетом сумм и округлением копеек:
// Процедура последовательного заполнения с дроблением остатков строк
// Параметры:
// ТаблицаТоваров - Исходная ТаблицаЗначений (колонки: Номенклатура, ЦенаРН, КоличествоРН, СуммаРН)
// КоличествоДокументов - На сколько документов разбиваем
Процедура РаспределитьПоследовательноСДроблением(ТаблицаТоваров, КоличествоДокументов)
// Добавим служебную колонку для управления обходом
Если ТаблицаТоваров.Колонки.Найти("Включать") = Неопределено Тогда
ТаблицаТоваров.Колонки.Добавить("Включать", Новый ОписаниеТипов("Булево"));
КонецЕсли;
ТаблицаТоваров.ЗаполнитьЗначения(Истина, "Включать");
ОбщаяСумма = ТаблицаТоваров.Итог("СуммаРН");
СредняяСумма = Окр(ОбщаяСумма / КоличествоДокументов, 2);
Для НомерДока = 1 По КоличествоДокументов Цикл
// Создаем новый документ или целевую таблицу
НовыйДокументТовары = ТаблицаТоваров.СкопироватьКолонки();
ТекущаяСуммаДокумента = 0;
// Получаем только те строки, которые еще не распределены полностью
Отбор = Новый Структура("Включать", Истина);
ВключаемыеТовары = ТаблицаТоваров.НайтиСтроки(Отбор);
Для Каждого СтрокаТЗ Из ВключаемыеТовары Цикл
Если ТекущаяСуммаДокумента >= СредняяСумма И НомерДока < КоличествоДокументов Тогда
// Документ уже набрал среднюю сумму, переходим к следующему
Прервать;
КонецЕсли;
ДоступнаяСумма = СредняяСумма - ТекущаяСуммаДокумента;
// Если строка целиком помещается в рамки средней суммы (или это последний документ)
Если СтрокаТЗ.СуммаРН <= ДоступнаяСумма Или НомерДока = КоличествоДокументов Тогда
НоваяСтрока = НовыйДокументТовары.Добавить();
ЗаполнитьЗначенияСвойств(НоваяСтрока, СтрокаТЗ);
ТекущаяСуммаДокумента = ТекущаяСуммаДокумента + СтрокаТЗ.СуммаРН;
// Помечаем строку как полностью отработанную
СтрокаТЗ.КоличествоРН = 0;
СтрокаТЗ.СуммаРН = 0;
СтрокаТЗ.Включать = Ложь;
Иначе
// Строка целиком не влезает. Пытаемся взять часть количества.
// Рассчитаем, сколько целых штук товара мы можем взять
Если СтрокаТЗ.ЦенаРН > 0 Тогда
ВозможноеКоличество = Цел(ДоступнаяСумма / СтрокаТЗ.ЦенаРН);
Иначе
ВозможноеКоличество = 0;
EndIf;
Если ВозможноеКоличество > 0 И ВозможноеКоличество < СтрокаТЗ.КоличествоРН Тогда
НоваяСтрока = НовыйДокументТовары.Добавить();
НоваяСтрока.Номенклатура = СтрокаТЗ.Номенклатура;
НоваяСтрока.ЦенаРН = СтрокаТЗ.ЦенаРН;
НоваяСтрока.КоличествоРН = ВозможноеКоличество;
НоваяСтрока.СуммаРН = Окр(ВозможноеКоличество * СтрокаТЗ.ЦенаРН, 2);
НоваяСтрока.Включать = Истина;
ТекущаяСуммаДокумента = ТекущаяСуммаДокумента + НоваяСтрока.СуммаРН;
// Корректируем остаток в исходной таблице
СтрокаТЗ.КоличествоРН = СтрокаТЗ.КоличествоРН - ВозможноеКоличество;
СтрокаТЗ.СуммаРН = Окр(СтрокаТЗ.КоличествоРН * СтрокаТЗ.ЦенаРН, 2);
СтрокаТЗ.Включать = (СтрокаТЗ.КоличествоРН > 0);
КонецЕсли;
КонецЕсли;
КонецЦикла;
// Здесь можно записать созданный НовыйДокументТовары в базу данных
// ...
КонецЦикла;
КонецПроцедуры
Анализ логики алгоритма: Обратите внимание на важный нюанс пересчета остатков строки. Мы не просто вычитаем количество, мы обязательно пересчитываем сумму остатка в исходной строке как КоличествоРН * ЦенаРН. Если этого не сделать, возникнет ситуация, когда сумма строки перестанет соответствовать количеству и цене, что приведет к искажению данных в последующих документах.
Также обратите внимание на условие НомерДока = КоличествоДокументов. При обработке последнего документа мы отключаем все лимиты и забираем все оставшиеся хвостики строк целиком. Это гарантирует, что весь товар без остатка будет распределен, а итоговый баланс сойдется до копейки.
Если исходная таблица содержит тысячи строк, частый обход коллекции с проверкой условий может замедлить работу алгоритма. Рассмотрим несколько советов по оптимизации кода в 1С:
ТаблицыЗначений с помощью метода Удалить(). На малых объемах данных (до 500 строк) это допустимо. Однако при больших объемах физическое удаление строк из памяти приводит к постоянному сдвигу индексов и падению производительности. Использование флага Включать или перенос ссылок на строки в отдельный служебный Массив работает значительно быстрее.Если Строка.Включать Тогда, лучше использовать встроенный быстрый метод платформы ТаблицаЗначений.НайтиСтроки() с отбором по структуре. Платформа делает это на уровне оптимизированного C++ кода, что существенно ускоряет работу.Итог("Сумма") при каждом вызове осуществляет полный обход колонки для суммирования. Если вызывать его внутри вложенных циклов, производительность упадет лавинообразно. Вместо этого ведите оперативную переменную накопленной суммы (как это сделано в наших примерах) и увеличивайте ее значение вручную при добавлении каждой строки.Подводя итоги нашего анализа, дадим практические рекомендации по выбору алгоритма:
Если специфика вашего учета позволяет распределять товары в случайном порядке (главное — равенство итоговых сумм), всегда выбирайте Решение 1 (Жадный алгоритм LPT с параллельным заполнением). Это классический, математически обоснованный подход. Он работает быстрее, не требует дробления упаковок товара и гарантирует минимальную погрешность без усложнения программного кода.
Если же вам необходимо строго последовательно заполнять один документ за другим и вы имеете право делить позиции на части, используйте Решение 2 (Последовательный подбор с расчетом остатков). При его реализации обязательно контролируйте округление сумм и корректность пересчета остатка по формуле Количество * Цена, чтобы избежать расхождения копеек в учете.