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