При автоматизации кассовых операций и расчетов с покупателями часто возникает задача: в документе отгрузки есть табличная часть с товарами (наименование, цена, количество), и поступает частичная оплата на определенную сумму. Требуется набрать товарные позиции так, чтобы их суммарная стоимость была не меньше суммы платежа, но при этом превышение (дельта) оказалось минимальным. В теории алгоритмов это классическая задача об ограниченном рюкзаке (Bounded Knapsack Problem) с ограничением «справа» (минимизация суммы при условии $\sum \ge S$).
Разберем, как реализовать такой подбор программно, какие математические алгоритмы работают быстрее всего и с какими фискальными коллизиями можно столкнуться при печати чеков по 54-ФЗ.
Перед тем как переходить к сложным математическим алгоритмам, проанализируем правовую и учетную сторону вопроса. Зачастую разработчики пытаются решить задачу целочисленного подбора товаров для кассового чека, создавая себе проблемы со сходимостью кассовых итогов.
"Оплата по накладной №...", количеством 1 и суммой, строго равной сумме платежа.«Количество предмета расчета» (тег 1023, до трех знаков после запятой). Это снимает необходимость дискретного перебора комбинаций.Если требуется вывести в чек реальные позиции накладной, самым надежным и простым методом является последовательный перебор строк с дроблением последней позиции. Сумма чека всегда сойдется копейка в копейку.
Рассмотрим логику работы алгоритма:
ОстатокСуммы / Цена), а копеечная погрешность округления корректируется в итоговой сумме строки.При повторных платежах по той же накладной уже оплаченные товары исключаются (для этого остатки по позициям фиксируются в регистре или рассчитываются по предыдущим чекам).
Если требуется строго целочисленное количество единиц товара, а частичная оплата закрывает существенную часть накладной (например, оплачено 90% отгрузки), прямая задача подбора работает медленно из-за огромного пространства комбинаций.
В этом случае эффективнее инвертировать задачу: вместо набора позиций на сумму $S$ мы ищем комбинацию товаров, которую нужно вычесть из накладной на сумму не более $(\text{СуммаВсехТоваров} - S)$.
// Пример инвертирования задачи набора
СуммаВсехТоваров = 0;
Для К = 1 По ТабТоваров.КоличествоСтрок() Цикл
СуммаВсехТоваров = СуммаВсехТоваров + ТабТоваров.ПолучитьЗначение(К, "Сумма");
КонецЦикла;
ЛишняяСумма = СуммаВсехТоваров - ИскомаяСумма;
Если ЛишняяСумма > 0 Тогда
// Ищем комбинацию, сумма которой <= ЛишняяСумма (классический рюкзак)
ТабЛишнихТоваров = ПодобратьРюкзакДо(ЛишняяСумма);
// Вычитаем лишнее из исходной корзины
Для К = 1 По ТабЛишнихТоваров.КоличествоСтрок() Цикл
НомСтр = 0;
Если ТабТоваров.НайтиЗначение(ТабЛишнихТоваров.ПолучитьЗначение(К, "Товар"), НомСтр, "Товар") = 1 Тогда
ТекКол = ТабТоваров.ПолучитьЗначение(НомСтр, "Количество");
ВычКол = ТабЛишнихТоваров.ПолучитьЗначение(К, "Количество");
ТабТоваров.УстановитьЗначение(НомСтр, "Количество", ТекКол - ВычКол);
КонецЕсли;
КонецЦикла;
КонецЕсли;
Когда требуется найти комбинацию с минимальным превышением заданной суммы, применяется метод ветвей и границ. Чтобы алгоритм укладывался в отведенные 1–2 секунды, применяются правила отсечения неперспективных ветвей перебора:
В строках накладной количество одного товара может достигать сотен и тысяч штук. Прямой перебор каждой единицы делает пространство вариантов колоссальным. Чтобы решить задачу ограниченного рюкзака (Bounded Knapsack) за доли секунды, применим двоичное разложение количеств.
Любое целое количество $K$ можно представить в виде суммы степеней двойки: $1, 2, 4, 8, \dots, K - (2^m - 1)$. Например, если салфеток 13 штук, мы разбиваем их на виртуальные «пачки» размером 1, 2, 4 и 6 штук. Из этих пачек можно составить любое число от 1 до 13. Таким образом, строка с тысячами единиц превращается всего в $\approx 10$ независимых элементов, и задача сводится к классическому рюкзаку 0-1.
Далее запускается одномерный массив динамического программирования, где индекс массива — это проверяемая сумма, а значение — признак ее достижимости (или индекс предмета, которым эта сумма была набрана). Поиск идет в диапазоне от ЦелеваяСумма до ЦелеваяСумма + МаксимальнаяЦена. Первая же достижимая сумма в этом диапазоне и будет математически точным решением с минимальной дельтой.
При переносе математических алгоритмов на платформу 1С 7.7 важно учитывать специфику ее среды исполнения:
СписокЗначений, ТаблицаЗначений) создают ощутимые накладные расходы при частых обращениях в циклах. Перед запуском тяжелого расчета выгрузим данные в простые массивы или типизированные структуры.Применяя бинарное разложение в связке с динамическим программированием либо метод ветвей и границ с отсечением по рекорду, подбор корзины из сотен позиций отрабатывает быстрее 0,5 секунды.