I am looking for an algorithm or method that can help me solve the following problem:

Given $N$ integers and $M$ buckets with a sum label How do I arrange the $N$ numbers so that each bucket has the closest $\Sigma(N)=M(\text{label})$.

Example if I have $N=\{5,10,6,2,1\}$ and $M=\{10,6,8\}$, how do I get the result of:




as the output, in the general case, I want to algorithm to give me the best approximation as my real-world use case can't guarantee that the summations will be exact.

Thank you

  • 1
    $\begingroup$ Are you allowed to reuse some of the numbers? Also what does "best approximation" mean? In any case, you might want to look into the "subset sum problem". $\endgroup$ Jun 22 at 23:05
  • $\begingroup$ This seems to be the Generalized assignment problem. $\endgroup$ Jun 23 at 4:30
  • $\begingroup$ You can't reuse numbers, best approx, means the lowest delta from M possible, with some numbers of N left behind $\endgroup$
    – David MZ
    Jun 23 at 10:00
  • $\begingroup$ It is not clear what try you to optimize. Let $L$ be the set of labels. For each $\ell \in L$, let $X_\ell$ be the integers you are going to put into the bucket with label $\ell$ and capacity $m_l$. I believe the delta you metion is something like $\delta_\ell \stackrel{def}{=} m_\ell - \sum\limits_{x\in X_\ell}x$. Do you want to minimize the average delta $\left(\frac1M\sum\limits_{\ell \in L}|\delta_\ell|^\alpha\right)^{\frac1{\alpha}}$ for some $\alpha > 0$ or the maximum delta $\max\limits_{\ell \in L}|\delta_\ell|$. Do you allow buckets to overflow, ie. some $\delta_\ell < 0$... $\endgroup$ Jun 23 at 10:34


Your Answer

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

Browse other questions tagged or ask your own question.