1
$\begingroup$

I have a discrete distribution of reference. For the example let's say:

  • P(X=1)=0.2
  • P(X=2)=0.7
  • P(X=3)=0.1

Now I am given n numbers, and I want to group (sum) those numbers into 3 bins and approximate as close as possible the above distribution in the sense of minimizing the sum of squared error. So let's say I have those numbers: 10, 25, 25 50 (total sum =100). So I want to group them into 3 bins, and ideally the sum of each bin would be 20, 70, 10 and that would perfectly match the distribution. Unfortunately that's not possible and the best here would be 25, 75 (50+25), 10. The error here is (25-20)²+(75-70)²+(10-10)²=50

What is the algorithm solving the general problem?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – dkaeae Jul 11 at 7:15
1
$\begingroup$

The case where $\Pr(X=1)=\Pr(X=2)=\tfrac12$ is the subset sum problem, which is NP-complete so you won't find an efficient algorithm in general. Dynamic programming is probably the way to go.

$\endgroup$

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.