В практике программирования на платформе 1С нередко возникает ситуация, когда имеется список чисел (например, суммы накладных или количества товаров) и целевое итоговое значение. Нам необходимо выяснить, какие именно строки из этого списка в сумме дают искомый результат. Эта задача в теории алгоритмов известна как «Задача о сумме подмножества» (Subset Sum Problem) и является частным случаем знаменитой «Задачи о ранце».
В данной статье мы подробно разберем, как подступиться к решению этой задачи, рассмотрим ограничения языка запросов 1С и реализуем эффективный алгоритм перебора на встроенном языке.
Первое желание программиста 1С — решить всё одним запросом. Однако здесь мы сталкиваемся с серьезным техническим препятствием. Язык запросов 1С (основанный на T-SQL) не поддерживает рекурсивные ОБЩИЕ ТАБЛИЧНЫЕ ВЫРАЖЕНИЯ (Recursive CTE). Без них построить универсальный запрос, который мог бы суммировать произвольное количество строк (от 2 до N), практически невозможно.
Рассмотрим попытку решения через перекрестное соединение (CROSS JOIN), если мы заранее предполагаем, что искомая сумма состоит, например, только из двух строк. Разберем этот пример, предложенный участниками сообщества:
Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ
| Таб.Зн КАК Зн
|ПОМЕСТИТЬ ВТ1
|ИЗ
| &Таб КАК Таб
|;
|
|ВЫБРАТЬ
| ВТ1.Зн КАК Зн1,
| ВТ11.Зн КАК Зн2
|ИЗ
| ВТ1 КАК ВТ1
| ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ1 КАК ВТ11
| ПО ВТ1.Зн < ВТ11.Зн
|ГДЕ
| ВТ1.Зн + ВТ11.Зн = &ИскомаяСумма";
Запрос.УстановитьПараметр("Таб", ТаблицаСДанными);
Запрос.УстановитьПараметр("ИскомаяСумма", 63);
Проанализируем этот код. Он сработает только в том случае, если сумма 63 складывается ровно из двух чисел. Если же сумма состоит из трех, четырех или более слагаемых, нам придется добавлять в запрос новые соединения (ВТ12, ВТ13 и т.д.). Поскольку количество строк в таблице заранее неизвестно, такой подход является «жестким» и не подходит для универсальных задач.
Наиболее надежным и гибким способом решения задачи о сумме подмножества в 1С является использование рекурсии. Мы будем последовательно перебирать варианты, складывая числа. Если текущая сумма совпала с искомой — мы нашли решение. Если сумма превысила искомую — мы возвращаемся на шаг назад (бэктрекинг) и пробуем другое число.
Разберем программный код, реализующий этот алгоритм:
Перем МассивЧисел, ИскомаяСумма, КоличествоЭлементов;
// ТекНабор - строка, хранящая текущую комбинацию слагаемых
// СуммаВх - накопленная сумма текущего набора
// ИндНач - индекс, с которого начинаем поиск в массиве
Процедура НайтиСуммуПодмножества(ТекНабор = "", СуммаВх = 0, ИндНач = 0)
Для Инд = ИндНач По КоличествоЭлементов - 1 Цикл
ТекущееЧисло = МассивЧисел[Инд];
НоваяСумма = СуммаВх + ТекущееЧисло;
Если НоваяСумма = ИскомаяСумма Тогда
// Ура! Мы нашли точное совпадение
Сообщить("Найдено решение: " + ТекНабор + " + " + ТекущееЧисло);
ИначеЕсли НоваяСумма < ИскомаяСумма Тогда
// Сумма пока меньше искомой, идем вглубь (рекурсия)
НайтиСуммуПодмножества(ТекНабор + " + " + ТекущееЧисло, НоваяСумма, Инд + 1);
КонецЕсли;
// Если НоваяСумма > ИскомаяСумма, цикл просто перейдет к следующему числу
КонецЦикла;
КонецПроцедуры
// Пример инициализации:
МассивЧисел = Новый Массив;
МассивЧисел.Добавить(37);
МассивЧисел.Добавить(47);
МассивЧисел.Добавить(16);
МассивЧисел.Добавить(5);
МассивЧисел.Добавить(2);
КоличествоЭлементов = МассивЧисел.Количество();
ИскомаяСумма = 63;
НайтиСуммуПодмножества("", 0, 0);
Давайте проанализируем, как работает этот алгоритм. Он использует метод «поиска с возвратом». Если мы передадим массив [37, 47, 16, 5, 2] и сумму 63, алгоритм проверит 37, затем 37+47 (превышение, возврат), затем 37+16... и в итоге найдет комбинацию 47 + 16 = 63.
Работая с подобными алгоритмами в 1С, необходимо учитывать несколько важных моментов:
Число с дробной частью), обязательно помните о проблемах точности чисел с плавающей запятой. Перед поиском лучше умножить все числа на 100 и привести их к целому виду, чтобы избежать ситуации, когда 0.1 + 0.2 не равно 0.3.Массив.O(n log n) и достаточно в 90% случаев.Если количество строк в таблице не превышает 31, мы можем применить изящный метод битовых масок. Каждое целое число от 1 до 2^N можно представить как битовую последовательность, где 1 означает, что строка с этим индексом включена в сумму, а 0 — нет. Пройдя циклом по всем числам, мы гарантированно проверим все возможные комбинации без использования рекурсии.
Рассмотрим этот подход подробнее. Для 5 строк нам нужно перебрать числа от 1 до 31 (2^5 - 1). Каждое число — это уникальный набор слагаемых. Это решение более надежно с точки зрения потребления памяти, так как не плодит уровни вложенности процедур.
Мы выяснили, что стандартными средствами языка запросов 1С задачу поиска суммы подмножества решить невозможно из-за отсутствия рекурсивных конструкций. Однако встроенный язык 1С позволяет эффективно реализовать алгоритм обхода дерева решений. Выбор метода (рекурсия, динамическое программирование или жадный алгоритм) должен зависеть от объема ваших данных и требуемой точности результата.