Как эффективно подобрать документы, сумма которых соответствует заданной цели?

Часто перед программистами 1С встает задача автоматического подбора документов из списка таким образом, чтобы их сумма максимально приближалась к заданному значению. На первый взгляд, это кажется классической задачей о рюкзаке или задачей о сумме подмножеств, однако при попытке реализации стандартных алгоритмов динамического программирования на языке 1С мы сталкиваемся с критическими проблемами: нехваткой оперативной памяти и низкой скоростью обработки больших массивов данных.

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

Почему классическое динамическое программирование не подходит для 1С?

Классический алгоритм, который использует создание матрицы (двумерного массива), требует выделения памяти пропорционально произведению количества элементов на целевую сумму. Если ваша цель — 10 000 рублей, а документов 100, массив будет содержать 1 000 000 ячеек. При увеличении суммы до 1 000 000 ячеек количество операций становится критичным для интерпретатора 1С, что приводит к зависанию или ошибке переполнения памяти.

Кроме того, если суммы документов имеют дробную часть (копейки), их необходимо приводить к целым числам (умножать на 100), что еще сильнее раздувает размерность матрицы. Мы должны осознать: 1С не предназначена для интенсивных математических вычислений в циклах с большой глубиной вложенности.

Варианты реализации задачи

Рассмотрим несколько эффективных стратегий, которые позволят решить задачу подбора суммы, не «убивая» производительность системы.

1. Жадный алгоритм с локальной оптимизацией

Этот метод не всегда дает математически идеальный результат, но он работает мгновенно и в большинстве бизнес-задач этого более чем достаточно.

1. Отсортируйте массив ваших документов по убыванию суммы.
2. Последовательно проходите по списку: если сумма текущего документа не превышает остаток требуемой суммы, включайте его в набор.
3. Для улучшения результата примените метод «локального спуска»: если после основного цикла осталось «пустое место», попробуйте заменить один или два уже выбранных документа на те, что не вошли в набор, чтобы сократить разницу до минимума.

2. Метод «Встреча посередине»

Если количество документов невелико (например, до 40-50 штук), можно использовать этот алгоритм:

• Разделите ваш исходный массив на две равные части.
• Сгенерируйте все возможные комбинации сумм для первой части и сохраните их в таблицу.
• Сделайте то же самое для второй части.
• Выполните поиск пар значений (одно из первой части, другое из второй), сумма которых наиболее близка к целевой.

3. Нормализация данных

Если суммы слишком велики, попробуйте их нормализовать. Например, вычислите наибольший общий делитель (НОД) для всех сумм. Если суммы кратны какому-то числу, разделите их на него. Это значительно уменьшит размерность данных, с которыми будет работать алгоритм.

Пример рекурсивного подхода (для малых выборок)

Хотя рекурсия может привести к переполнению стека при больших объемах, для небольшого количества элементов она позволяет быстро описать логику перебора:

Функция ПолучитьСуммуРекурсивно(_Массив, _Индекс, _Сумма)
    _См = _Массив[_Индекс].Значение;
    Если _См = _Сумма Тогда
        Возврат _См;
    КонецЕсли;
    
    Для иии = _Индекс + 1 по _Массив.РазмерМассива Цикл
        _тСм = _Массив[_Индекс + 1].Значение;
        Если _тСм <= _Сумма - _См Тогда
            _См = _См + ПолучитьСуммуРекурсивно(_Массив, иии, _Сумма);
        КонецЕсли;
    КонецЦикла;
    
    Возврат _См;
КонецФункции

Практические рекомендации

При разработке алгоритмов подбора в 1С следуйте этим принципам:

• Ограничивайте глубину поиска. Не пытайтесь перебрать абсолютно все сочетания, если документов больше 20-30.
• Используйте предварительную сортировку. Она ускоряет работу любого алгоритма.
• Комбинируйте методы. Например, используйте «жадный алгоритм» для быстрого заполнения, а затем сделайте «доводку» оставшейся части суммы коротким перебором.
• Избегайте создания огромных массивов Массив в оперативной памяти. Если данных много, лучше выгружать их во временные таблицы (ТЗ) или использовать индексы для быстрого поиска.

В завершение, помните: если задача требует сложной оптимизации, не бойтесь вынести расчет в отдельный сервис или внешнюю обработку, работающую на более производительных языках, но для 99% бизнес-задач комбинация «жадного» поиска с последующей локальной корректировкой является идеальным решением.