# How to create a subset with a given length and mean?

I have a set of numbers $$P=\{p_1,\dotsc,p_{|P|}\}$$, where $$|P|$$ is the length of the set. I want to select a subset, $$S$$, from $$P$$ such that its mean is approximately equal to a predefined value $$\mu_s$$ .

$$\sum_{x \in S} x \approx \mu_s * |S|$$ My problem:

• $$|P|$$ = 5000
• $$|S|$$ = 1500
• $$\mu_s$$ $$\approx$$ 90 $$(target$$ $$mean)$$
• $$\mu_p$$ = 95
• $$min(P)$$ = 0
• $$max(P)$$ = 300

I am looking for algorithm suggestions so I can implement this in Python. I would also like $$S$$ to include a range of values, rather than just the naive approach of sorting from smallest to largest first, then applying a greedy algorithm.

Additional question is whether dynamic programming could be used for this type of problem (i.e. we have to select a certain number of items from a list such that the sum is as close as possible to the capacity limit)?

• 1. By "length" do you mean "size"? 2. "I would like $S$ to include a range of values" isn't a criterion that can be incorporated in an algorithm. – j_random_hacker Jan 20 at 5:45
• (If you don't like a particular solution, one approach is to remove some/all of the chosen elements from $P$ and rerun.) – j_random_hacker Jan 20 at 5:46
• Since $|S|$ is specified as the input, this is simply the ordinary Subset Sum problem (or equivalently, Knapsack with all values equal to 1) with target weight $|S|\mu_s$. – j_random_hacker Jan 20 at 5:49
• What does the notation $\mu_p$ represent? – D.W. Jan 20 at 6:13
• Hi @j_random_hacker, yes by length I mean size. I agree, the way I am currently trying to solve it is by treating it as a knapsack problem where all values are equal to 1 and with the addition requirement that I use 1500 numbers exactly. – Jwem93 Jan 20 at 9:00

For every $$i \in \{0,\ldots,|P|\}$$, $$j \in \{0,\ldots,|S|\}$$, and $$T \in \{0,\ldots,\mathcal{T}\}$$ (I discuss $$\mathcal{T}$$ below), compute whether there is a subset of size $$j$$ of $$p_1,\ldots,p_i$$ which sums to $$T$$. You should take $$\mathcal{T}$$ to be your maximum allowable answer – $$\max(P) \cdot |S|$$ would definitely do, but you can probably pick something which is closer to $$\mu_S |S|$$, say $$\mu_P |S|$$. The running time is $$O(|P| |S| \mathcal{T})$$. In your case, assuming you choose $$\mathcal{T} \approx \mu_p |S|$$, then $$|P| |S| \mathcal{T} \approx 2^{40}$$, so this is barely feasible.
For example, you could only look for solutions such that $$S \cap \{0,\ldots,i\} \approx \frac{|S|}{|P|} i$$ and $$\sum(S \cap \{0,\ldots,i\}) \approx \frac{|S|}{|P|} \mu_S$$, which will reduce the running time significantly. While this is only a heuristic, it might be possible to show that you get a decent approximation on average, if you randomize the order of $$P$$.
Another possible optimization is to quantize the partial sums, quantizing more aggressively as $$i$$ gets larger. If done carefully, you won't lose much in accuracy but will have a significant gain in running time.