Sum of subsets with special conditions

Question

(Before you answer with a link to another SO question or close it as a duplicate, read the question carefully. This is different from the standard version of this problem, and I searched for a long time, so I'm pretty sure there is no such question)

I need to find if the smallest possible S , which is the sum of some subset of X [i] , which is > = T (some target value less than the sum of the complete set).

The set is not very large (about 40 elements), but still too large for an exponential solution to reverse tracing.

the numbers and the amount are huge (about 10 ^ 15), so dynamic programming will not work (the number of possible states is large, so the memory table will end soon in the notes table).

For the same reason, the Pisinger linear time algorithm will not work (this is O (nr), where r is the upper bound of the sum, which in this case is too large).

Is there any deterministic algorithm that will help me in this case with a large sum, but few digits? I do not want to resort to some approximation algorithms.

Answer 1

Given these conditions, I believe that solving the inverse problem with a branch and snapping is your best shot to get the exact solution.

The idea is to check all subsets, but you can trim the computation tree for some possible subsets at runtime.

For example, suppose you are looking for S = 10^8 , and you have already found the solution sol=10^8 + 10^7 . Now you check all the subsets that are supersets of some X , and you find that sum(X) = 10^9 , There is no need to constantly check any subsets containing X , you can just skip them - they will not be optimal.

I would also try to parallelize the solution, the branch and the related connection are easily parallelized usually, you just need to synchronize a new better solution from time to time.

Answer 2

As you said, the set was not very large (about 40). I think the classic O(2^(n/2) n) exponential time algorithm will fit your needs http://en.wikipedia.org/wiki/Subset_sum_problem#Exponential_time_algorithm .

I can briefly describe the approach here. Divide the set into two equal sizes, say A and B. And list the sum of the subsets for them to create two sets of size 2^(n/2) , for example PA and PB. Then you can sort PA and PB and use binary search to find the sum exceeding T in time O(2^(n/2) n) .