# Quantity allocation algorithm performance

I have a scenario for which I'll take an analogous example to help understand better.

There are N buckets of known varying capacities. We have `M` balls that we need to put in these buckets to fill them fully or partially. The existing algorithm works as below:

For each bucket calculate the fraction `effect = (Bi + 1)/Ci` where `Bi` and `Ci` is the current number of balls in the bucket and capacity of `ith` bucket respectively. Identify the bucket with the lowest effect and put a ball in it taking from M. Repeat the above process until there are no balls left(`M=0`) or all buckets are filled to the capacity.

The above algorithm produces the desired output but it has performance issues when there are a large number of buckets and many balls to allocate. The inner loop must run `M * N` to allocate all the balls.

I tried optimizing it by allocating the balls in bulk to each bucket. The new approach is as below:

For each bucket, do this: calculate the difference(no. of balls short of full capacity) `Di = Ci - Bi`. calculate the no. of balls to put in bucket as `Mi = (Di * M)/S` where S is sum of differences(D1+D2....Dn) for all buckets.

Although, its much faster but results are not the same as the previous approach especially in case there are insufficient balls to fill all buckets.(i.e M < S)

Can anyone suggest an algorithm that is almost independent of `M` and produces the same output as the original approach that allocates one ball at a time?