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 polynomial 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?