1
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ – j_random_hacker Jan 20 at 5:45
  • 1
    $\begingroup$ (If you don't like a particular solution, one approach is to remove some/all of the chosen elements from $P$ and rerun.) $\endgroup$ – j_random_hacker Jan 20 at 5:46
  • 1
    $\begingroup$ 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$. $\endgroup$ – j_random_hacker Jan 20 at 5:49
  • $\begingroup$ What does the notation $\mu_p$ represent? $\endgroup$ – D.W. Jan 20 at 6:13
  • $\begingroup$ 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. $\endgroup$ – Jwem93 Jan 20 at 9:00
1
$\begingroup$

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.

This is a naive dynamic programming algorithm, which probably can be improved, especially since you're only looking for an approximation.

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.

$\endgroup$
1
  • $\begingroup$ Thanks @Yuval for your help, I will take a look at your suggestions. My current approach uses dynamic programming where I also include a condition that the subset be a certain size (all values are the same). It works, but it can be improved $\endgroup$ – Jwem93 Jan 20 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.