Алгоритм, который сообщает, можно ли получить число из заданного набора, используя только '+', '*' и скобки

Question

У меня есть два списка чисел, для каждого члена второго я должен сказать, можно ли его получить, используя все номера первого и помещая '+' или '*' и столько же '(' ')' Iхочу.
Я не могу изменить порядок.

List1 может содержать не более 20 элементов от 1 до 100.
List2 может содержать не более 5 элементов от 1 до 20 000.

EX:

List1=[2 4 3 5]  
List2=[19 15 24]

19-> 2+(4*3)+5  YES   
15              NO
24->2*(4+3+5)   YES

При использовании грубой силы требуются годы для обработки входов со списком List1 больше 10.

edit: числа всегда положительные.

edit: Я нахожу максимальные и минимальные числа, которые можно получить из списка, а затем я отбрасываю все возможности, у которых цель находится за пределами этого диапазона, затем я пробую все оставшиеся.

 MAX=n1*n2*n3*....*ni    if there are 1 thei r added to their smallest neighbour

 MIN=n1+n2+....+ni       1 excluded

Тем не менее, это не быстродостаточно, когда ввод велик (List1 длиннее 10 или числа в List2 крупнее 10000)

Answer 1

@ uu правильно, но я дам немного больше подробностей.

Предположим, что n = size of list 1.Для каждого 0 <= i < j < n вам нужно вычислить все различные значения в диапазоне (1..20_000), которые могут быть получены из чисел в интервале [i, j-1].Вы можете сделать это с помощью рекурсии и запоминания.

Как только вы это сделаете, проблема станет легкой.

Answer 2

Для каждого подсписка List1 вычислите числа от 1 до 20000, которые можно создать с помощью этого подсписка.Получившийся DP имеет сходство с CYK .

Здесь я немного расплывчат, потому что это почти наверняка является проблемой соревнования по программированию.

Answer 3

Вы можете попробовать умную грубую силу, которая отбрасывает системы уравнений кусками.