Алгоритм для комбинационных значений

Question

Я пытался написать алгоритм для данной задачи:

нам дан набор чисел- {n1, n2, n3, n4, n5 ......} и мы должны проверить, можем ли мы получить число (скажем, X), используя сложение и вычитание по заданным числам. X всегда будет меньше всех элементов данного набора.

Например.

Набор: {2,3,4,6,9}
заданное число: 1, результат: да
9-4-4 = 1

Набор: {3,4,6,9}
заданное число: 2, результат: да
6-4 = 2

Заранее спасибо.

Answer 1

Эффективно вы ищете идеал , сгенерированный числами в вашем наборе. Промежуточные числа образуют область главных идеалов , что означает, что каждый идеал генерируется одним целым числом. Все, что вам нужно сделать, это найти это единственное целое число - скажем, g - и проверить, можно ли разделить X на g. Найти g также легко - это наибольший общий делитель всех элементов в вашем наборе, который можно найти с помощью евклидова алгоритма .

Ваши примеры наборов могут генерировать каждое целое число путем сложения и вычитания, так как они могут генерировать 1. Например, для набора {3,4,6,9} у вас есть 1 = 4-3, и любое целое число n может быть записано как n раз сумма 4-3.

Answer 2

Исходя из вашего первого примера, что вы можете использовать число несколько раз.

Заданное число должно быть кратным GCD вашего набора. Это единственное условие. Неважно, насколько он велик.

Если вам нужен только ответ Да / Нет, то достаточно найти GCD. Если вам также нужно выражение для заданного числа , проблему можно заменить на поиск выражения для GCD.

GCD = X+Y+..+Z-T-U-...-V