An algorithm that indicates whether it is possible to get a number from a given set using only '+', '*' and brackets

Question

I have two lists of numbers, for each member of the second I have to say if he is available using all the numbers of the first and putting '+' or '*' and as many ('') 'I want.
I can not change the order.

List1 can contain a maximum of 20 items between 1 and 100.
List2 can contain a maximum of 5 items between 1 and 20'000.

Example:

List1=[2 4 3 5] List2=[19 15 24] 19-> 2+(4*3)+5 YES 15 NO 24->2*(4+3+5) YES 

Using brute force to process entries with List1 is greater than 10. It takes age.

edit: numbers are always positive.

edit: I find the max and min numbers that can be obtained from the list, and then I drop all the possibilities that have a goal outside this range, then I try to use all the others.

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

However, it is not fast enough when the input is large (List1 is greater than 10 or the number in List2 is greater than 10,000)

Answer 1

For each List1 sublist, calculate the numbers from 1 to 20,000 that can be made with this sublist. The resulting DP is similar to CYK .

I am a bit vague because it is almost certainly a programming problem.

Answer 2

@u is crazy, but I will tell you a little more.

Suppose n = size of list 1 . For each 0 <= i < j < n you need to calculate all the individual values ​​in the range (1..20_000), which can be made from numbers in the interval [i, j-1] . You can do this with recursion and memoization.

Once you have done this, the problem will be easy.

Answer 3

You can try smart brute force, which throws away a lot of equations in pieces.