В практике автоматизации учета на платформе 1С часто возникает задача распределения поступивших денежных средств по имеющимся документам задолженности (заказам, счетам или накладным). Типовые механизмы обычно предлагают распределение по методу FIFO (первым оплачивается самый старый долг) или по конкретным номерам счетов. Однако существует специфический запрос: распределить сумму оплаты так, чтобы «погасить» как можно большее количество заказов, независимо от их даты. Рассмотрим, как реализовать такой алгоритм, проанализируем математическую подоплеку и разберем программную реализацию.
Представим ситуацию: у контрагента есть множество неоплаченных заказов на разные суммы (от копеечных до крупных). Он присылает платеж на произвольную сумму. Наша цель — очистить список заказов от максимального количества строк. Проанализируем ситуацию: чтобы закрыть как можно больше документов, нам в первую очередь нужно выбирать заказы с минимальными суммами. В программировании такой подход называется «жадным алгоритмом» (Greedy Algorithm).
Жадный алгоритм на каждом шаге выбирает локально оптимальное решение (самый дешевый заказ), надеясь в итоге получить глобально оптимальный результат (максимальное число закрытых заказов). В данной конкретной постановке это решение является математически точным и оптимальным.
Разберем по шагам, как реализовать этот метод в 1С. Для работы нам понадобится таблица заказов, содержащая суммы, и переменная с суммой оплаты.
ТаблицаЗначений.Сумма в порядке возрастания.Проанализируем пример кода, реализующий этот подход:
// Предположим, ТЗ_Заказы содержит колонки "Заказ" и "Сумма"
// СуммаОплаты - сумма, поступившая от клиента
ТЗ_Заказы.Сортировать("Сумма Возр");
ОстатокОплаты = СуммаОплаты;
СписокОплаченныхЗаказов = Новый Массив;
Для Каждого СтрокаЗаказа Из ТЗ_Заказы Цикл
Если ОстатокОплаты >= СтрокаЗаказа.Сумма Тогда
// Суммы хватает для полного закрытия заказа
ОстатокОплаты = ОстатокОплаты - СтрокаЗаказа.Сумма;
СписокОплаченныхЗаказов.Добавить(СтрокаЗаказа.Заказ);
Иначе
// Суммы недостаточно для следующего по весу заказа
// Согласно ТЗ, остаток можно отбросить или оставить висеть
Прервать;
КонецЕсли;
КонецЦикла;
Этот метод гарантирует, что вы закроете максимально возможное число документов. Рассмотрим подробнее преимущества: алгоритм работает мгновенно (сложность O(n log n) из-за сортировки), прост в отладке и понятен пользователю.
Если же задача стоит шире — найти «все возможные комбинации» заказов, которые в сумме дают число, максимально близкое к оплате, — мы сталкиваемся с классической NP-полной задачей. Рассмотрим ситуацию, когда заказы имеют суммы 100, 200, 300, а оплата составляет 500. Мы можем закрыть {100, 200} или {200, 300} или {100, 300}.
Для поиска всех вариантов проанализируем метод рекурсивного обхода (бэктрекинг). Выясним причину, по которой этот метод стоит использовать с осторожностью: при большом количестве заказов (более 20-30) количество комбинаций растет экспоненциально, что может привести к зависанию системы.
Пример логики рекурсивной функции для поиска комбинаций:
Процедура НайтиКомбинации(ТекущийИндекс, ТекущаяСумма, ВыбранныеЗаказы)
// Если сумма превысила лимит - выходим
Если ТекущаяСумма > СуммаОплаты Тогда
Возврат;
КонецЕсли;
// Если мы дошли до конца списка заказов - сохраняем результат
Если ТекущийИндекс > ЗаказыМассив.ВТГраница() Тогда
Если ТекущаяСумма > 0 Тогда
СохранитьРезультат(ВыбранныеЗаказы, ТекущаяСумма);
КонецЕсли;
Возврат;
КонецЕсли;
// Вариант 1: Включаем текущий заказ в выборку
ЗаказИнфо = ЗаказыМассив[ТекущийИндекс];
ВыбранныеЗаказы.Добавить(ЗаказИнфо.Заказ);
НайтиКомбинации(ТекущийИндекс + 1, ТекущаяСумма + ЗаказИнфо.Сумма, ВыбранныеЗаказы);
// Вариант 2: Пропускаем текущий заказ (откат)
ВыбранныеЗаказы.Удалить(ВыбранныеЗаказы.Количество() - 1);
НайтиКомбинации(ТекущийИндекс + 1, ТекущаяСумма, ВыбранныеЗаказы);
КонецПроцедуры
Чтобы ограничить «комбинаторный взрыв», рекомендуется внедрять счетчик найденных решений и прерывать выполнение после нахождения первых 50–100 подходящих вариантов.
При реализации подобных алгоритмов в 1С важно помнить о производительности встроенного языка. Разберем несколько практических советов:
Массив структур или ТаблицаЗначений для расчетов. Избегайте постоянного обращения к базе данных (через точку от ссылки СтрокаЗаказа.Заказ.Сумма) внутри цикла. Сначала выгрузите всё в память.Окр(Сумма, 2), чтобы избежать проблем с точностью чисел с плавающей точкой, которые могут помешать точному сравнению сумм.Запрос.Необходимо учитывать, что «красивое» распределение оплат с точки зрения математики может быть некорректным с точки зрения бухгалтерии. Рассмотрим подробнее, почему:
Во-первых, в большинстве учетных политик закреплен метод FIFO. Произвольное закрытие мелких заказов вместо старых может привести к неверному расчету сроков исковой давности. Во-вторых, если заказы привязаны к разным договорам или ставкам НДС, хаотичное распределение создаст проблемы в налоговом учете.
Вывод: Жадный алгоритм через сортировку по возрастанию — идеальный инструмент для «технической» очистки базы от мелких долгов или для KPI по количеству закрытых сделок. Однако для серьезного финансового учета всегда оставляйте пользователю возможность ручной корректировки предложенной алгоритмом комбинации.