Subset sum with special conditions

Question

(Before you reply with a link to another SO question or close this as a duplicate please read the question carefully. This is different than the standard variant of this problem and I've searched for a long time so I'm pretty sure there isn't a question like this here)

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

The set isn't very large (about 40 elements), but still too big for exponential backtracking solution.

The numbers and the sum are huge (about 10^15), so dynamic programming won't work (The number of possible states is large so the memoization table would soon run out of memory).

For the same reason the linear time algorithm by Pisinger won't work (it's O(nr) where r is the upper bound on the sum, which is too big in this case).

Is there some deterministic algorithm that will help me in this case of large sum but few numbers? I don't want to resort to some approximation algorithm.

Emera

Answer 1

Given the mentioned conditions, I believe a backtracking solution with branch & bound is your best shot to get the exact solution.

The idea is to check all subsets, but you can trim the calculation tree for some possible subsets during the run of the algorithm.

For example, assume you are looking for S = 10^8, and you already found a solution of sol=10^8 + 10^7, Now, you are checking all subsets that are supersets of some X, and you find out that sum(X) = 10^9. There is no need to keep checking any subsets that contain X, you can simply skip them - they will not get you optimal.

I'd also try to parallelize the solution, branch and bound is easily parallelized usually, just need to synchronize the new best solution once in a while.

Subtlety

Answer 2

As you said that the set wasn't very larget(around 40). I think the classic exponential time algorithm of complexity O(2^(n/2) n) will fit your need http://en.wikipedia.org/wiki/Subset_sum_problem#Exponential_time_algorithm.

I can briefly describe the approach here. Split the set into two equal size set, say A and B. And enumerate the subset sum for them to generate two set of size 2^(n/2), say PA and PB. Then you can sort PA and PB and use binary search to find the sum that exceeds T in time O(2^(n/2) n).

Moreville