Как проверить, можно ли получить какое-то число в результате суммирования или разности заданных чисел
У меня есть произвольный список положительных целых чисел и некоторое число X. Я хочу проверить, можно ли получить X, используя базовые операции, такие как суммирование и разность.
Любой номер из списка можно использовать только один раз. Могут быть дубликаты.
Мы можем использовать любое количество чисел из списка, чтобы получить X, т. е. мы можем использовать только один элемент, можно использовать также два элемента и можно использовать все элементы из списка.
Достаточно только ответа «Верно/Неверно».
Например:
input_list=[1, 7, 3]
X = 4
результат: TRUE (например: 7-3)
input_list=[1, 7, 3]
X = 50
результат: FALSE
Я попытался использовать подход из этого вопроса: Найдите все комбинации списка чисел с заданной суммой,
конкретно эта часть:
[seq for i in range(len(numbers), 0, -1)
for seq in itertools.combinations(numbers, i)
if sum(seq) == target]
Моя идея заключалась в том, чтобы объединить исходный список со списком противоположных целых чисел:
new_list = input_list+list(map(lambda x: -x, input_list))
Затем я проверяю, возвращает ли описанная выше операция понимания списка непустой список.
Но это занимает слишком много времени, что мне не нравится, так это то, что в этом подходе есть какое-то дублирование, itertools.combinations может дважды принимать 1, а наоборот -1, но я понятия не имею, как это исправить.
Каков наиболее эффективный способ решения такой проблемы?
Вы спрашиваете, какой самый эффективный способ решения этой проблемы, но я подозреваю, что вам просто нужен работающий и не очень неэффективный способ? (это другой вопрос) Насколько велик список входных данных, учитывая, что вы говорите, что «это занимает слишком много времени» для начала решения, которое у вас было с itertools.combinations?
7-3+1 = 5, так почему же результат второго примера будет ложным?
Также обратите внимание, что добавление всех противоположностей к исходному списку позволит получить суммы типа -3-7 = -10, что вам может понадобиться - или нет.
Еще следует отметить, что вы не указали точную проблему, например, можно ли повторно использовать числа? Есть ли в списке повторяющиеся номера? Разрешены ли комбинации из более чем одного числа или вы ищете только пары? Вас интересует только правильный/неправильный ответ или вам нужно фактическое решение? Пожалуйста, будьте конкретны и расскажите о своей попытке, независимо от ее результатов.
Спасибо всем за отзывы, я обновил вопрос, чтобы сделать его более понятным. Что касается моей попытки, то это по сути копипаста из связанного вопроса (но исходный список целых чисел объединяется с его противоположностями)
Что вы подразумеваете под «например» в «основных операциях, таких как суммирование и разность»? В зависимости от того, включаете ли вы * или % в этот список, ответы могут сильно различаться.
Это можно смоделировать как линейную целочисленную программу, в которой каждая переменная должна быть равна 0 или 1. Пусть L — заданный список натуральных чисел, где i-е число обозначено Li. Пусть переменная Pi равна 1, если Li должна быть включена в сумму, иначе равна 0, и пусть Ni равна 1, если -Li должна быть включена в сумму, иначе равна 0. Единственное ограничение — SUM(over i)LiPi + SUM(over i)-LiNi = X. Целевая функция произвольна (скажем, max 0P1). Если для некоторых i, Pi = 1 и Ni = 1 при оптимальном наборе Pi = 0 и Ni = 0.
Ответы 2
Наивный подход имел бы временную сложность O(N ^ 2):
def _diff(nums, x):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == x or abs(nums[i] - nums[j]) == x:
return True
return False
print(_diff([1, 7, 3], 4))
print(_diff([1, 7, 3], 5))
Мы можем использовать set(), чтобы сделать его немного более эффективным:
def check_sum_diff(nums, x):
S = set(nums)
for num in nums:
if (x + num in S) or (num - x in S):
return True
return False
print(check_sum_diff([1, 7, 3], 4))
print(check_sum_diff([1, 7, 3], 5))
Принты
True
False
Вы тестируете только комбинации из двух чисел, в то время как ОП ожидает найти комбинации любой длины.
@ThierryLathuille Я это пропустил. Спасибо!
По каждому номеру в списке вам предстоит принять решение:
- ты добавляешь номер
- ты вычитаешь число
- ты скинь номер
Вот решение с поиском в ширину дерева решений:
def isRepresentable(input_list, num):
reachable = { 0 }
for n in input_list:
reachable = { y for x in reachable for y in [x, x + n, x - n] }
if num in reachable:
return True
return False
print(isRepresentable([1, 7, 3], 4)) # True
print(isRepresentable([1, 7, 3], 50)) # False
print(isRepresentable([1, 7, 3], 5)) # True
BFS находит более короткие решения, но DFS также подойдет для истинных/ложных ответов.
Если кто-то также хочет увидеть, как можно построить число, ему необходимо сохранить путь, ведущий к этому числу:
def findRepresentation(input_list, num):
reachable = { 0: [] }
for n in input_list:
next_reachable = dict(reachable)
for x in reachable:
for y in [x, x + n, x - n]:
if y not in next_reachable:
next_reachable[y] = [*(reachable[x]), y - x]
if num == y:
return next_reachable[y]
reachable = next_reachable
return None
def explain(input_list, num):
print(f'Using {input_list}')
print(f'{num} = {findRepresentation(input_list, num)}')
explain([1, 7, 3], 4) # 4 = [1, 3]
explain([1, 7, 3], 50) # None
explain([1, 7, 3], 5) # 5 = [1, 7, -3]
hundred_primes = [
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101, 103, 107,
109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193,
197, 199, 211, 223, 227, 229, 233, 239,
241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337,
347, 349, 353, 359, 367, 373, 379, 383,
389, 397, 401, 409, 419, 421, 431, 433,
439, 443, 449, 457, 461, 463, 467, 479,
487, 491, 499, 503, 509, 521, 523, 541
]
explain(hundred_primes, 2024)
Не то чтобы кто-то спрашивал, но 2024 год можно представить как сумму первых 33 простых чисел, если пропустить 103:
2024 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 107, 109, 113, 127, 131, 137, 139]
Связанный вопрос должен найти все комбинации. Вам нужно только выяснить, существует ли какая-либо комбинация. Это можно рассматривать как форму задачи о рюкзаке 0-1 , где числа действуют как вес и значение, применяемые к вашему
new_list, содержащему отрицательные копии. Вы можете решить эту проблему достаточно эффективно с помощью динамического программирования. См. stackoverflow.com/questions/47608725/knapsack-but-exact-weight