В практике разработчика 1С часто возникает задача: из большого массива документов (например, РеализацияТоваровУслуг) выбрать такой набор, сумма которого максимально близка к числу, введенному пользователем, но не превышает его. Эта задача является классическим примером из области информатики и математики, известным как «Задача о рюкзаке» (Knapsack Problem) или «Задача о сумме подмножеств».
В этой статье мы подробно разберем, как реализовать эффективный подбор документов, проанализируем различные подходы — от простых «жадных» алгоритмов до точных методов динамического программирования — и выясним, как оптимизировать код для работы с большими данными.
Прежде чем приступать к написанию кода, проанализируем условия. Пользователь вводит целевую сумму (например, 10 000 рублей). Нам необходимо просмотреть документы за определенный период и найти их комбинацию, которая в сумме даст ровно 10 000 или максимально близкое к этому значение «снизу» (то есть <= 10 000).
Важно понимать, что «наиболее подходящий» набор может определяться разными критериями:
Жадный алгоритм — это самый простой способ решения. Суть его заключается в том, что на каждом шаге мы выбираем самый «выгодный» на данный момент элемент. В нашем случае — документ с наибольшей суммой, который еще помещается в остаток целевой суммы.
Рассмотрим реализацию этого метода. Сначала мы выбираем все подходящие документы запросом, сортируя их по убыванию суммы. Это критически важно для работы жадного алгоритма.
&НаСервере
Процедура ПодобратьЖаднымАлгоритмом(ЦелеваяСумма, ДатаНач, ДатаКон)
Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ
| РТиУ.Ссылка КАК Ссылка,
| РТиУ.СуммаДокумента КАК Сумма
|ИЗ
| Документ.РеализацияТоваровУслуг КАК РТиУ
|ГДЕ
| РТиУ.Дата МЕЖДУ &ДатаНач И &ДатаКон
| И РТиУ.Проведен = ИСТИНА
| И РТиУ.СуммаДокумента <= &ЦелеваяСумма
|УПОРЯДОЧИТЬ ПО
| Сумма УБЫВ";
Запрос.УстановитьПараметр("ДатаНач", ДатаНач);
Запрос.УстановитьПараметр("ДатаКон", ДатаКон);
Запрос.УстановитьПараметр("ЦелеваяСумма", ЦелеваяСумма);
РезультатЗапроса = Запрос.Выполнить();
Выборка = РезультатЗапроса.Выбрать();
ТекущаяСумма = 0;
МассивРезультат = Новый Массив;
Пока Выборка.Следующий() Цикл
Если (ТекущаяСумма + Выборка.Сумма) <= ЦелеваяСумма Тогда
МассивРезультат.Добавить(Выборка.Ссылка);
ТекущаяСумма = ТекущаяСумма + Выборка.Сумма;
КонецЕсли;
// Если набрали идеально, выходим сразу
Если ТекущаяСумма = ЦелеваяСумма Тогда
Прервать;
КонецЕсли;
КонецЦикла;
// Вывод результата пользователю...
КонецПроцедуры
Преимущества: Высокая скорость работы, простота реализации, минимальное потребление памяти.
Недостатки: Алгоритм не всегда находит оптимальное решение. Например, если цель — 100, а у нас есть документы [60, 50, 50], жадный алгоритм возьмет 60 и на этом остановится (остаток 40, 50 не лезет), хотя комбинация [50, 50] дала бы идеальный результат.
Для получения гарантированно лучшего результата проанализируем метод динамического программирования. Мы будем строить таблицу, где для каждой возможной суммы от 0 до ЦелеваяСумма будем хранить информацию о том, можно ли ее достичь и с помощью каких документов.
Чтобы сэкономить память, вместо двумерного массива будем использовать одномерный массив КартаДостижимости, где индексом будет выступать сумма (в копейках, чтобы избежать проблем с точностью Число), а значением — структура с данными о документах.
Разберем по шагам реализацию с учетом специфики 1С:
Функция НайтиОптимальныйНабор(ЦелеваяСумма, СписокДокументов)
// Переводим в копейки для точности и использования в качестве индекса
Множитель = 100;
Лимит = ЦелеваяСумма * Множитель;
// Массив, где индекс - это сумма, а значение - индекс документа,
// который позволил достичь этой суммы
Предки = Новый Массив(Лимит + 1);
ДостижимаяСумма = Новый Массив(Лимит + 1);
ДостижимаяСумма[0] = Истина; // Нулевая сумма достижима всегда
Для Каждого Док Из СписокДокументов Цикл
ТекущаяЦена = Док.Сумма * Множитель;
// Идем с конца в начало, чтобы не использовать один документ дважды
Для сч = Лимит По ТекущаяЦена Шаг -1 Цикл
Если ДостижимаяСумма[сч - ТекущаяЦена] = Истина И ДостижимаяСумма[сч] = Неопределено Тогда
ДостижимаяСумма[сч] = Истина;
Предки[сч] = Док; // Запоминаем, какой документ привел к этой сумме
КонецЕсли;
КонецЦикла;
КонецЦикла;
// Ищем максимально близкую к Лимиту сумму, которая стала Истиной
НайденнаяСумма = 0;
Для сч = Лимит По 0 Шаг -1 Цикл
Если ДостижимаяСумма[сч] = Истина Тогда
НайденнаяСумма = сч;
Прервать;
КонецЕсли;
КонецЦикла;
// Восстанавливаем набор документов
Результат = Новый Массив;
ВременнаяСумма = НайденнаяСумма;
Пока ВременнаяСумма > 0 Цикл
Док = Предки[ВременнаяСумма];
Результат.Добавить(Док.Ссылка);
ВременнаяСумма = ВременнаяСумма - (Док.Сумма * Множитель);
КонецЦикла;
Возврат Результат;
КонецФункции
Важное замечание: Метод динамического программирования потребляет объем памяти, пропорциональный целевой сумме. Если пользователь введет 1 000 000, массив на 100 000 000 элементов (копеек) может вызвать переполнение памяти процесса rphost. В таких случаях суммы стоит округлять до рублей или использовать другие методы.
Рассмотрим ситуацию, когда документов очень много, и динамическое программирование не подходит по памяти. Мы можем применить улучшенную логику из Сообщения 52: выполнить жадный перебор, но в конце сделать проверку — не станет ли сумма ближе к цели, если мы заменим последний добавленный документ на следующий по списку (который чуть больше остатка).
Проанализируем этот алгоритм:
При реализации подобных алгоритмов необходимо учитывать производительность платформы. Выясним основные правила оптимизации:
СуммаДокумента обычно не проиндексировано в типовых конфигурациях. Если вы планируете часто делать выборки с условием по сумме или сортировкой, рассмотрите возможность добавления индекса (хотя для документов это делается редко из-за влияния на скорость проведения).Ссылка и СуммаДокумента. Работать с компактной таблицей значений в памяти гораздо быстрее, чем с выборкой объектов.Новый Структура("Ссылка, Сумма", Ссылка, Сумма) работает быстрее, чем обращение к свойствам объекта документа через точку в цикле.Сумма1 = Сумма2. Всегда используйте небольшую дельту (эпсилон) или переводите числа в целые (копейки), как показано в примере с динамическим программированием.Для случаев, когда количество документов невелико (до 40), но суммы огромные (что делает динамическое программирование невозможным), рассмотрим алгоритм «Встреча посередине». Мы делим список документов на две равные части. Для каждой части генерируем все возможные суммы подмножеств. Затем сортируем один из списков сумм и для каждой суммы из второго списка ищем «пару» в первом с помощью бинарного поиска (МетодНайти() в 1С для этого не подойдет, нужно реализовать свой бинарный поиск по массиву).
Это позволяет сократить сложность перебора с $2^{40}$ до $2^{21}$, что вполне реально выполнить за разумное время на современном сервере 1С.
Подбор документов по сумме — это классическая задача оптимизации. Если вам достаточно «хорошего» решения, используйте жадный алгоритм с предварительной сортировкой. Если требуется «идеальное» решение и суммы небольшие — используйте динамическое программирование. Для сложных случаев с миллионными оборотами лучше всего подойдут эвристические методы или масштабирование (деление всех сумм на 10 или 100 для снижения размерности задачи).