# How to arrange $N$ values into $M$ buckets with fixed sum?

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:

$$10=10$$

$$6=5+1$$

$$8=6+2$$

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

• 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". Jun 22 at 23:05
• This seems to be the Generalized assignment problem. Jun 23 at 4:30
• You can't reuse numbers, best approx, means the lowest delta from M possible, with some numbers of N left behind Jun 23 at 10:00
• 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$... Jun 23 at 10:34