В процессе работы с данными в 1С часто возникают нестандартные задачи. Одна из таких — имеется большой перечень положительных чисел (слагаемых), и необходимо из них выбрать такое подмножество, которое в сумме даст определенное, заранее заданное значение. Например, в отчете с множеством строк нужно подобрать строки так, чтобы итоговая сумма стала равна конкретному числу.
Эта задача известна в информатике как «Задача о сумме подмножеств» (Subset Sum Problem). Она является частным случаем более общей «Задачи о рюкзаке». Важно сразу понимать, что эта задача относится к классу NP-полных. Говоря простым языком, это означает, что не существует известного алгоритма, который бы гарантированно находил точное решение за короткое время для больших объемов данных. Полный перебор всех возможных комбинаций (а их 2N, где N — количество слагаемых) становится невозможным уже при нескольких десятках элементов. Для 5000 слагаемых, как в исходной проблеме, это число просто астрономическое.
Рассмотрим, какие подходы можно применить для решения этой задачи в 1С, оценив их сложность, точность и применимость на практике.
Это самый очевидный и легко реализуемый метод, который часто приходит в голову первым. Он не гарантирует нахождения точного решения, но может дать приемлемый результат, особенно если допустима некоторая погрешность.
Разберем по шагам, как его реализовать:
ТаблицуЗначений или СписокЗначений и его метод Сортировать().Преимущества:
Недостатки:
Пример. Допустим, нам нужно набрать сумму 20 из набора чисел: [12, 11, 9, 8, 5, 2, 1].
А теперь другой пример. Сумма та же 20, набор: [12, 11, 9, 8, 5, 2, 1]. Нужно набрать 19.
Кажется, что все хорошо. Но посмотрим на такой случай. Сумма 16, набор: [10, 8, 8, 5, 3].
Результат "жадного" алгоритма — 15, погрешность 1. А ведь точное решение существует: 8 + 8 = 16. "Жадный" алгоритм его не нашел.
Этот метод представляет собой "умный" перебор. Вместо того чтобы проверять все 2N комбинаций, мы будем строить дерево решений и отсекать заведомо проигрышные ветви. Этот подход гораздо медленнее "жадного", но способен найти точное решение.
Основная идея:
Мы пишем рекурсивную процедуру, которая для каждого слагаемого из списка решает, брать его в итоговую сумму или не брать.
индекс + 1), а в качестве оставшейся суммы передаем текущая_оставшаяся_сумма - значение_текущего_элемента.индекс + 1) с той же самой оставшейся суммой.Производительность:
В худшем случае этот алгоритм все равно переберет все варианты. Но на практике, благодаря отсечениям (например, если оставшаяся сумма меньше нуля), он работает значительно быстрее. Для набора из 20-30 элементов он найдет решение за секунды. Для 200-300 элементов (как упоминалось в обсуждении на форуме) он также может отработать за приемлемое время. Однако для 5000 элементов этот метод неприменим.
Это классический академический метод решения данной задачи. Он гарантирует нахождение точного решения, но имеет серьезные ограничения по памяти и времени, связанные с величиной искомой суммы.
Идея:
Строится таблица (двумерный массив), где по одной оси отложены слагаемые (от 1 до N), а по другой — все возможные суммы (от 1 до S, где S — искомая сумма). Каждая ячейка [i][j] в этой таблице будет хранить ответ на вопрос: "Можно ли набрать сумму j, используя только первые i слагаемых?"
Ограничения:
Сложность этого алгоритма O(N * S). Это означает, что время его работы и требуемая память прямо пропорциональны произведению количества слагаемых на величину искомой суммы. Если в нашей задаче N = 5000, а S = 10 000 000, то нам понадобится таблица размером 5000 * 10 000 000, что невозможно реализовать ни на одной современной системе, тем более в 1С 7.7.
Вывод: данный метод подходит только для задач с небольшим количеством элементов и небольшой искомой суммой.
Проанализировав ситуацию, можно дать следующие рекомендации для решения задачи в 1С:
В конечном итоге, для задачи с 5000 слагаемых и необходимостью набрать сумму в несколько миллионов, наиболее реалистичным путем является использование простого и быстрого "жадного" алгоритма, с пониманием его ограничений и возможной неточности.