Мне поручено помочь некоторым бухгалтерам решить общую проблему, которую они имеют, - учитывая список транзакций и общий депозит, какие транзакции являются частью депозита? Например, скажем, у меня есть этот список чисел:
1.00
2.50
3.75
8.00
И я знаю, что мой общий депозит 10.50
, я легко вижу, что он состоял из транзакций 8.00
и 2.50
. Однако, учитывая сто транзакций и депозит в миллионах, это быстро становится намного сложнее.
При тестировании решения грубой силы (которое слишком длительное, чтобы быть практичным) у меня было два вопроса:
-
Со списком около 60 номеров, похоже, найдется дюжина или более комбинаций для любой общей суммы, которая разумна. Я ожидал, что одна комбинация удовлетворит мою общую или, возможно, несколько возможностей, но всегда кажется, что есть тонна комбинаций. Есть ли математический принцип, который описывает, почему это? Кажется, что, учитывая набор случайных чисел даже среднего размера, вы можете найти многократную комбинацию, которая суммируется примерно до любой суммы, которую вы хотите.
-
Я создал решение для грубой силы для проблемы, но, очевидно, O (n!), и быстро выходит из-под контроля. Помимо очевидных ярлыков (исключая числа, которые больше, чем сама сумма), есть ли способ сократить время, чтобы вычислить это?
Информация о моем текущем (сверх медленном) решении:
Список подробных сумм сортируется от наибольшего до наименьшего, а затем следующий процесс выполняется рекурсивно:
- Возьмите следующий элемент в списке и посмотрите, добавляет ли его к вашей общей сумме общее совпадение цели. Если это так, выделите текущую цепочку как совпадение. Если он не соответствует вашей цели, добавьте его в текущее общее количество, удалите его из списка подробных сумм и снова вызовите этот процесс.
Таким образом, это исключает большие числа быстро, сокращая список до только чисел, которые необходимо учитывать. Тем не менее, он все еще п! и более крупные списки никогда не заканчиваются, поэтому меня интересуют любые ярлыки, которые я могу предпринять, чтобы ускорить это - я подозреваю, что даже вырезание 1 номера из списка сократило бы время вычисления пополам.
Спасибо за вашу помощь!