Choosing subsets of a set such that the subsets satisfy a global constraint

We have a set of items I = {i_1, i_2, ..., i_n}. Each of these items has what we call a p value, which is some real number. We want to choose a subset of I, call it I', of size m (for some m with 1 <= m <= n) such that the average of the p values of the items in I' falls within some specified range, [p_l, p_u]. (For example, we might require an average p value between 0.70 and 0.74.) Moreover, we want to do this efficiently.

We hope to do this in O(n) time, but any pol开发者_运维问答ynomial time algorithm is good enough. We certainly do not want to just try every possible subset of I of size m and then check whether it satisfies the average p-value constraint.

Finally, we will be doing this repeatedly and we want the subsets chosen to be a uniformly random distribution over all the possible such subsets.

Is there a way of doing this?

If you have a subset and its sum, if you scale the sum by |subset+1|/|subset|, each new element you add contributes linearly to the sum. This thus seems extremely similar to the subset-sum problem (NP-complete), where the goal is to find all subset which sum to 0, albeit here we wish the sum to be close to 0. For example, if you have a large set where one element is roughly in the acceptable p-range, if you make the sketchy assumption that that element doesn't matter, suddenly it is practically equivalent... assuming you have a large number of positive and negative p-values, and the problem is not constructed by an adversary. If this is the case, you could use one of the two approximating solutions given at http://en.wikipedia.org/wiki/Subset_sum_problem , make the equality "fuzzy", and just tack on a "reserved" element with 0.7<p<0.74 to the set.

Of course the efficiency you can eek out of your solution is incredibly dependent on the way p-values are generated (the "distribution" thereof).