Sorting Numbers into Groups

Question

I have a list of numbers N1,N2,N3…………

The list must be grouped into groups of 3 G1,G2,G3…..

The sum of Each Group must be >= X, The sum of Each Group must be <= Y

I understand that there may be some numbers left over that cannot be grouped.

1. What is the best way to group the numbers such that the maximum number of groups can be created ?
2. What is the best way to group the numbers such that groups can be created in the least amount of time ?
3. Is there a best case combination of requirement 1 and 2 ?

thanks Damo

Answer 1

I'm not going to write proper pseudocode, but I think that a near-optimal algorithm would just pair the largest numbers with the smallest ones.

First, you can't have a best/worst case for condition 1 without knowing the range of your data set. The worst case is always zero (all N are greater than Y) and the best case is 100%

My recommended algorithm:

1 - Sort N, a quicksort algorithm has time complexity O(n log n), from this point I will refer to the smallest value in the list as N(1) and the largest as N(t)

2 - If N(t) + N(t-1) + N(1) < X, remove N(1), repeat until false

3 - If N(t) + N(1) + N(2) > Y, remove N(t), repeat until false

4 - Pair N(t) + N(t-1) + N(1) or N(t) + N(1) + N(2) into a group, whichever is closest to (X+Y)/2, return to step 2.

This is almost definitely not the best algorithm, but any major improvements will probably involve some fairly complex optimization, and I wouldn't even be sure where to begin. I hope this helps a bit!