В практике разработчика 1С часто возникает задача: имеется список из множества строк (например, неоплаченные накладные или авансы), и необходимо выбрать из них такую комбинацию, сумма которой максимально близко или точно совпадает с целевым значением (например, суммой платежного поручения). В программировании эта классическая проблема известна как "Задача о сумме подмножеств" или частный случай "Задачи о рюкзаке".
Проблема заключается в том, что при большом количестве строк (от 100 и выше) полный перебор всех возможных комбинаций становится невозможным из-за экспоненциального роста сложности. Если в списке 1000 строк, количество комбинаций составит 2 в 1000-й степени, что не под силу ни одному современному серверу. Рассмотрим эффективные алгоритмы и подходы, которые позволяют решить эту задачу в среде 1С.
Рассмотрим наиболее простой программный подход. Мы можем реализовать алгоритм, который последовательно перебирает элементы, начиная с разных стартовых позиций, и накапливает сумму, пока она не приблизится к целевой. Этот метод не гарантирует 100% точности, но работает быстро и подходит для ситуаций, когда допустима небольшая погрешность.
Проанализируем пример кода, который реализует такой подход. Мы создаем таблицу приближений, куда записываем результаты проходов по массиву данных:
&НаСервере
Функция ИндексыСуммПриближения(ТаблицаСумм, СуммаКритерий)
ТаблицаПриближений = Новый ТаблицаЗначений;
ТаблицаПриближений.Колонки.Добавить("Сумма", Новый ОписаниеТипов("Число"));
ТаблицаПриближений.Колонки.Добавить("Отклонение", Новый ОписаниеТипов("Число"));
ТаблицаПриближений.Колонки.Добавить("Индексы");
ВГраницаСтрок = ТаблицаСумм.Количество()-1;
// Проходим циклом, меняя стартовую точку подбора
Для СчетчикСтарта = 0 По ВГраницаСтрок Цикл
СуммаКПогашению = СуммаКритерий;
Приближение = ТаблицаПриближений.Добавить();
Приближение.Индексы = Новый Массив;
Приближение.Индексы.Добавить(СчетчикСтарта);
ТекСуммаНакопленная = 0;
Для СчетчикПрохода = СчетчикСтарта По ВГраницаСтрок Цикл
СтрокаПрохода = ТаблицаСумм[СчетчикПрохода];
ТекЗначение = СтрокаПрохода.Сумма;
// Если добавление числа не превышает порог или это первый элемент
Если (ТекСуммаНакопленная + ТекЗначение) <= СуммаКритерий Тогда
ТекСуммаНакопленная = ТекСуммаНакопленная + ТекЗначение;
Приближение.Индексы.Добавить(СчетчикПрохода);
КонецЕсли;
Если ТекСуммаНакопленная == СуммаКритерий Тогда
Прервать; // Идеальное совпадение
КонецЕсли;
КонецЦикла;
Приближение.Сумма = ТекСуммаНакопленная;
Приближение.Отклонение = СуммаКритерий - ТекСуммаНакопленная;
Если Приближение.Отклонение == 0 Тогда
Прервать;
КонецЕсли;
КонецЦикла;
ТаблицаПриближений.Сортировать("Отклонение Возв");
Если ТаблицаПриближений.Количество() > 0 Тогда
Возврат ТаблицаПриближений[0].Индексы;
КонецЕсли;
Возврат Неопределено;
КонецФункции
В данном примере мы используем жадную стратегию: берем элементы по порядку, пока они "влезают" в остаток суммы. Повторение цикла с разных позиций позволяет найти более удачную комбинацию, чем при простом ФИФО.
Если требуется высокая точность, разберем более сложный, но эффективный метод — метод ветвей и границ. Его суть заключается в построении дерева решений, где на каждом шаге мы либо включаем текущее число в сумму, либо нет. Чтобы не перебирать всё дерево, мы применяем правила отсечения:
Для реализации в 1С рекомендуется использовать рекурсивную функцию. Однако помните о лимите стека рекурсии при работе с 1000 строк. В таких случаях лучше использовать стек на основе объекта Массив или ТаблицаЗначений.
Выясним, когда эффективно динамическое программирование. Этот метод идеально подходит, если целевая сумма — это целое число и оно не слишком велико (например, до 100 000). Мы создаем массив Булево размером ЦелеваяСумма + 1.
Алгоритм действий:
ДостижимыеСуммы, где индекс 0 равен Истина.i достижима, то сумма i + ТекущееЧисло также становится достижимой.Этот метод позволяет за один проход по списку чисел определить все возможные суммы, которые можно составить. Для восстановления самих элементов (какие именно числа дали сумму) обычно хранят индекс последнего добавленного элемента для каждой достижимой суммы.
Проанализируем ситуацию, когда данных очень много (тысячи строк), а время на расчет ограничено (не более нескольких секунд). В этом случае целесообразно использовать метод случайного поиска или упрощенный генетический алгоритм:
Важный совет: Для ускорения работы в 1С при использовании случайного поиска старайтесь минимизировать обращения к метаданным и объектам БД внутри цикла. Работайте с простыми типами данных (массивы чисел).
При реализации любого из перечисленных алгоритмов стоит учитывать специфику платформы 1С:
ТаблицыЗначений или тем более РезультатаЗапроса внутри тяжелых алгоритмов сильно замедляет работу.Число (целое) перед началом вычислений. Это позволит использовать индексы массивов в динамическом программировании и избежать ошибок округления Double.Подведем итог: для 1000 строк в 1С оптимальным выбором будет либо жадный алгоритм с несколькими итерациями (как в примере кода выше), либо метод случайного поиска с локальным улучшением. Эти подходы обеспечивают отличный баланс между скоростью разработки, производительностью системы и качеством подбора сумм.