Математика и алгоритмы 1С 8.3 1С:ERP Управление предприятием 2
Привет, коллеги! Сегодня хочу поделиться одной интересной наработкой, которая родилась из вполне прикладной задачи: как быстро подобрать набор чисел (отрезков, весов, стоимостей) из заданного множества так, чтобы их сумма была максимально близка к целевому значению. Казалось бы, классическая задача о сумме подмножества, которая решается либо полным перебором (2^n комбинаций), либо динамическим программированием (O(n * сумма)). Но когда n переваливает за несколько десятков, а целевая сумма может быть большой, классические методы в 1С начинают либо тормозить, либо требовать слишком много памяти.
Я пошёл другим путём – создал вероятностный алгоритм, который за фиксированное количество итераций выдаёт результат с очень высокой точностью (в 99% случаев фактическая сумма совпадает с целевой, если, конечно, есть из чего её собирать). Причём работает он на удивление быстро и без зависаний. Давайте разберём его устройство.
1 стартмани
12
