Search code examples
ralgorithmbin-packing

Filling bins with an equal size

I have 100 groups and each group has some elements inside. For the cross validation, I want to make five bins which their size is as equal as possible.

Is there any algorithm for this purpose.

An example for 5 groups and 2 bins:

Group_1: 5
Group_2: 6
Group_3: 2
Group_4: 7
Group_5: 1

The two bins will be:

G1 and G2 -> their sum is equal to 11.

G3, G4 and G5 -> their sum is equal to 10.

Solution

  • This seems related to the set partitioning problem, which is NP-hard but fortunately admits lots of good approximation algorithms and pseudopolynomial-time dynamic programming algorithms. You may want to look into those as a starting point, since there's already quite a lot of work that's been done in this area.

    Hope this helps!