В процессе разработки учетных систем на платформе 1С программисты часто сталкиваются с необходимостью распределения платежей. Типовой сценарий — автоматическое закрытие долгов по ФИФО (хронологический порядок). Однако иногда бизнес-логика требует более сложного подхода: нужно распределить входящую оплату по заказам так, чтобы закрыть как можно большее количество документов полностью, не допуская частичной оплаты и не оставляя нераспределенного остатка копеек. Рассмотрим, как решить эту алгоритмическую задачу на платформе 1С 8.3 с использованием управляемых форм.
На первый взгляд задача кажется тривиальной. В обсуждениях часто предлагают использовать простой «жадный» алгоритм: отсортировать заказы по сумме от меньшего к большему и последовательно оплачивать их, пока не закончатся деньги. Проанализируем, почему этот метод не всегда работает.
Представим ситуацию: у нас есть неоплаченные заказы на суммы 100, 200, 300 и 900 рублей. Контрагент перечисляет платеж в размере 1000 рублей. По условиям задачи мы должны распределить оплату полностью и закрыть заказы только целиком.
В математике и программировании эта проблема известна как «задача о сумме подмножеств» (Subset Sum Problem), которая является частным случаем классической «задачи о рюкзаке» (Knapsack Problem). Она относится к классу NP-полных задач, а значит, простого и быстрого аналитического решения для любого объема данных не существует. Нам придется подбирать комбинации программно.
Если бизнес-требования допускают частичное закрытие последнего заказа, на который не хватило полной суммы, мы можем использовать простой и быстрый алгоритм. Он работает за линейное время и идеально подходит для стандартных задач взаиморасчетов.
Разберем по шагам его реализацию в общем модуле или модуле объекта 1С. Сначала мы выбираем запросом все неоплаченные заказы по контрагенту, сортируем их по дате (или по возрастанию суммы для максимизации количества закрытых документов) и последовательно распределяем сумму:
// Функция распределяет сумму по таблице заказов по методу ФИФО
Процедура РаспределитьОплатуЖаднымМетодом(ТаблицаЗаказов, Знач СуммаОплаты) Экспорт
Для Каждого СтрокаЗаказа Из ТаблицаЗаказов Цикл
Если СуммаОплаты <= 0 Тогда
Прервать;
КонецЕсли;
// Вычисляем, сколько осталось доплатить по заказу
НеоплаченныйОстаток = СтрокаЗаказа.СуммаДокумента - СтрокаЗаказа.СуммаОплаты;
Если НеоплаченныйОстаток <= 0 Тогда
Продолжить;
КонецЕсли;
Если СуммаОплаты >= НеоплаченныйОстаток Тогда
// Оплачиваем заказ полностью
СтрокаЗаказа.СуммаОплаты = СтрокаЗаказа.СуммаОплаты + НеоплаченныйОстаток;
СуммаОплаты = СуммаОплаты - НеоплаченныйОстаток;
Иначе
// Оплачиваем заказ частично на оставшиеся деньги
СтрокаЗаказа.СуммаОплаты = СтрокаЗаказа.СуммаОплаты + СуммаОплаты;
СуммаОплаты = 0;
КонецЕсли;
КонецЦикла;
КонецПроцедуры
Этот код надежен, быстр и легко масштабируется на тысячи документов. Но если частичная оплата запрещена, нам потребуется полноценный перебор подмножеств.
Для выполнения условий автора темы (полная оплата без остатка и вывод всех возможных комбинаций пользователю на форму) напишем алгоритм рекурсивного поиска. Программа будет ветвить вычисления: на каждом шаге она либо включает текущий заказ в гипотетическую оплату, либо пропускает его.
Для оптимизации и исключения проблем с дробными числами при сравнении (проблема представления чисел с плавающей точкой в памяти компьютера) рекомендуется предварительно умножить все суммы на 100, превратив их в целые числа (копейки). Выясним причину: сравнение Сумма1 = Сумма2 для вещественных чисел в редких случаях может вернуть ложь из-за микроскопической погрешности округления.
Рассмотрим код рекурсивного поиска комбинаций, который можно разместить в модуле управляемой формы обработки:
&НаСервере
Процедура НайтиВариантыРаспределенияНаСервере()
// Подготавливаем исходный массив сумм заказов (переводим в копейки)
СписокЗаказов = Новый Массив;
Для Каждого СтрокаТаблицы Из Объект.Заказы Цикл
СтруктураЗаказа = Новый Структура;
СтруктураЗаказа.Вставить("Ссылка", СтрокаТаблицы.Заказ);
СтруктураЗаказа.Вставить("СуммаВКопейках", Цел(СтрокаТаблицы.Сумма * 100));
СписокЗаказов.Добавить(СтруктураЗаказа);
КонецЦикла;
ЦелеваяСуммаКопеек = Цел(Объект.СуммаОплаты * 100);
Результаты = Новый Массив;
ТекущийНабор = Новый Массив;
// Сортируем массив по убыванию сумм для ускорения работы рекурсии (отсечение ветвей)
// Чем раньше мы получим превышение целевой суммы, тем быстрее алгоритм вернется назад
БыстраяСортировкаЗаказовПоУбыванию(СписокЗаказов);
// Запускаем рекурсивный обход с нулевого индекса
ПоискПодмножествРекурсивно(0, 0, ТекущийНабор, СписокЗаказов, ЦелеваяСуммаКопеек, Результаты);
// Выводим результаты в таблицу на форме
ЗаполнитьТаблицуВариантовНаФорме(Результаты);
КонецПроцедуры
&НаСервере
Процедура ПоискПодмножествРекурсивно(Знач Индекс, Знач ТекущаяСумма, ТекущийНабор, СписокЗаказов, ЦелеваяСумма, Результаты)
// Проверяем базовое условие успешного поиска
Если ТекущаяСумма = ЦелеваяСумма Тогда
// Найдена подходящая комбинация заказов
Результаты.Добавить(ПолучитьКопиюМассива(ТекущийНабор));
Возврат;
КонецЕсли;
// Условия выхода (превышение суммы или конец списка документов)
Если ТекущаяСумма > ЦелеваяСумма Или Индекс >= СписокЗаказов.Количество() Тогда
Возврат;
КонецЕсли;
ТекущийЗаказ = СписокЗаказов[Индекс];
// Вариант 1. Включаем текущий заказ в комбинацию
ТекущийНабор.Добавить(ТекущийЗаказ.Ссылка);
ПоискПодмножествРекурсивно(Индекс + 1, ТекущаяСумма + ТекущийЗаказ.СуммаВКопейках, ТекущийНабор, СписокЗаказов, ЦелеваяСумма, Результаты);
// Вариант 2. Исключаем текущий заказ из комбинации (откат назад)
ТекущийНабор.Удалить(ТекущийНабор.Количество() - 1);
ПоискПодмножествРекурсивно(Индекс + 1, ТекущаяСумма, ТекущийНабор, СписокЗаказов, ЦелеваяСумма, Результаты);
КонецПроцедуры
&НаСервере
Функция ПолучитьКопиюМассива(ИсходныйМассив)
Копия = Новый Массив;
Для Каждого Элемент Из ИсходныйМассив Цикл
Копия.Добавить(Элемент);
КонецЦикла;
Возврат Копия;
КонецФункции
Проанализируем работу этого алгоритма. Он гарантированно найдет абсолютно все точные комбинации заказов, которые в сумме дают копейка в копейку сумму платежа клиента. Результаты можно вывести в правую таблицу на форме, сгруппировав их по номерам вариантов.
Важное ограничение: Рекурсивный перебор имеет экспоненциальную сложность O(2^N), где N — количество неоплаченных заказов. Если у контрагента накопилось более 25-30 открытых заказов, выполнение этого кода может привести к значительному замедлению работы или даже аварийному завершению сеанса 1С из-за переполнения стека вызовов. Обязательно ограничивайте количество обрабатываемых документов на входе!
Если документов много (более 30), а суммы не слишком велики, можно применить подход динамического программирования. Вместо рекурсивных вызовов мы строим двумерную матрицу промежуточных состояний. В 1С ее аналогом может служить ТаблицаЗначений или многомерный Массив.
Для этого создается таблица, где строками являются наши заказы, а колонками — все целочисленные значения сумм от 0 до целевой суммы оплаты (с шагом в 1 копейку). Каждая ячейка хранит булево значение: можно ли набрать сумму колонки с помощью текущего подмножества заказов. Заполнив таблицу по простым формулам, мы можем легко восстановить все возможные комбинации за полиномиальное время.
Однако в реальных бизнес-приложениях 1С к таким сложным математическим вычислениям прибегают редко. На это есть веские причины.
С точки зрения методологии бухгалтерского и управленческого учета, автоматический подбор «красивых» комбинаций документов под сумму платежа таит в себе скрытые опасности. Рассмотрим их подробнее:
// Пример распределения суммы пропорционально коэффициентам с помощью БСП
МассивКоэффициентов = Новый Массив;
МассивКоэффициентов.Добавить(100); // Вес первого документа
МассивКоэффициентов.Добавить(200); // Вес второго документа
РаспределеннаяСумма = ОбщегоНазначенияКлиентСервер.РаспределитьСуммуПропорциональноКоэффициентам(300.15, МассивКоэффициентов);
// На выходе получим массив с распределенными суммами с учетом копеек
Подводя итог, отметим: если вы столкнулись с подобной задачей на собеседовании или в рамках учебного тестирования, оптимальным решением будет демонстрация понимания ограничений рекурсивного подхода и применение сортировки для отсечения «заведомо ложных» ветвей вычислений. В реальных же проектах всегда отдавайте приоритет стандартной хронологической схеме ФИФО или ручному указанию счетов учета в платежных документах.