Временная сложность алгоритма исчерпывающего поиска

у меня есть наборы $S_1=\{2,10,20,6\}$ и $S_2=\{25,26,20\}$ и я хочу найти, сумма каких чисел дает 32. Это очень легко проверить; 6 и 26. Похоже на задачу о рюкзаке, но я не специалист.

Однако, скажем, у меня есть 1000 наборов, каждый из которых содержит 500 элементов, так что суммирование одного термина из каждого набора всегда дает вам уникальное значение. Это гораздо сложнее проверить и решить, особенно если наборы следуют структуре, которая будет казаться случайной (они будут построены из структурированных наборов, с которыми перепутались, и будет почти невозможно угадать смешивание и поменять местами наборы).

Таким образом, единственным способом должен быть алгоритм исчерпывающего поиска. Учитывая, что мой номер 52 485 332, есть $1000^{500}$ возможные варианты для просмотра. Действительно, будут способы сократить этот поиск (например, когда в наборе есть числа, превышающие ваше целевое значение, вы можете игнорировать эти числа). Но в противном случае вы могли бы все еще смотреть на $750^{500}$ возможные варианты.

Итак, какова временная сложность такого алгоритма поиска? $ О (п ^ {к}) $, с $n$ количество комплектов и $к$ количество элементов в этих множествах? Они должны проверить «все» возможные комбинации терминов, пока одна из них не совпадет с заданным значением.

Основные вопросы, кажется, "сколько есть наборов?" и «насколько велики наборы?». Ведь множества тоже могут быть разного размера, а не только одинаковые.

Я не криптограф; мое исследование просто заигрывает с идеей под рукой. Любая помощь будет оценена по достоинству.

Таким образом, единственным способом должен быть алгоритм исчерпывающего поиска.

Как я уже упоминал в своем комментарии, существуют практические методы для не очень больших значений $м$ (и $м=52485332$ не велик). Вот схема одного из таких методов (который предполагает, что все наборы состоят из неотрицательных целых чисел):

• У нас есть массив $A_{n, m+1}$; каждый элемент массива $А_{а, б}$ отметим, как мы можем сгенерировать сумму $b$ с самого начала $а$ наборы (или $\перп$ если такой способ еще не найден).

• Инициализировать все элементы $А$ к $\перп$

• За $я := 1$ к $n$ искать элементы $А_{я-1}$ для не-$\перп$ элемент (и для $я=1$, 0-й элемент рассматривается как единственный не-$\перп$ элемент. Для каждого такого элемента $A_{i-1, x}$, установлен $A_{i, x + S_{i,j}}$ к $j$ (для каждого элемента $S_{i,j}$ набора $S_i$) Если $x + S_{i,j} > m$, игнорируй это.

• Наконец, если $A_{n,m} = \perp$, нет подмножества, приводящего к сумме $м$. Если это что-то другое, мы можем восстановить термины, просматривая массив с возвратом. $А$.

Это должен быть практичный алгоритм восстановления терминов с заданными вами параметрами.

Это скорее ответ на вопрос, почему уникальность сумм так сильно влияет на размер, что случай для $52485332$ становится тривиальным (это слишком долго для комментария).

Когда все суммы должны быть уникальными, они должны давать разные целые числа. Потому что есть $500^{1000}$ возможные суммы, есть также $500^{1000}$ различные целые результаты для этого. в самом нижнем случае будут все целые числа из $0$ к $500^{1000}-1$.

Например,

$S_1 = \{0, 1, 2,..., 499\}$

$S_2 = \{0, 500, 1000,..., 249500\}$

$S_3 = \{0, 250000, 500000, ..., 124750000\}$

...

$S_{1000} = \{0, 500^{999}, 2*500^{999}, ..., 499*500^{999}\}$

способ гарантировать уникальность результата. Как видите, Числа становятся действительно большими очень быстро.

В этом конкретном примере легко найти результат (просто всегда выбирайте наибольшее число, которое подходит от последнего к первому набору). Даже большинство чисел $S_3$ больше, чем $52485332$ и поэтому может быть проигнорировано.

Вероятно, вам нужны относительно случайные значения в ваших наборах. В этом случае диапазон значений должен быть хотя бы немного больше.

Однако крайне маловероятно, что какое-либо значение ниже или равно $52485332$ (когда вы равномерно выбираете $500000$ значения из $500^{1000}$)

Динамическое программирование, как предложил @poncho, действительно работает только для небольших чисел, и его производительность не намного лучше, чем полный поиск (линейная разница в количестве наборов), потому что подсуммы, которые можно повторно использовать, уникальны, преимущество не смотреть на другие возможности не существует. Время выполнения должно быть в том же порядке, что и полный поиск. Единственное улучшение заключается в том, чтобы принять решение, когда значения слишком велики или малы для достижения цели, но для разумных целей это не является большим преимуществом.

Он может легко свести задачу о сумме подмножеств или задачу о рюкзаке к этой, просто используя один и тот же набор столько раз, сколько нужно суммировать.Проблема в том, что это не полиномиальное сокращение времени, поэтому его недостаточно для доказательства, если проблема NP-сложная.