Move List of Numbers into X Groups of (as close to) Equal Sum Value

[shaclark]

Hi everyone!

Several years ago, a user posted a question (773432) which was resolved: how to organize a list of values into two groups of (as close to) equal sum value. The answer was deftly provided by user "nimrod," who provided the following VBA code (see below).

A new user then asked the question which is also now my problem: What needs to be done to expand this VBA code to support X groups, rather than just two?

That question was not answered, but I would tremendously appreciate anyone's assistance in doing that now. For me, x=6, specifically, but it is beyond me to understand what would be needed to expand the two groups to six.

Thank you in advance! Code previously provided follows...

Scott

Please Login or Register  to view this content.

[MrShorty]

Do you understand the algorithm being used and how the code works? How much of your question is how to edit VBA and how much is more generic scaling up the algorithm and whether it is appropriate for your specific problem?

Walking through the code, the algorithm looks something like:

1) Figure out the approximate sum for each subgroup. Since we are dividing the data into 2 approximately equal subgroups:
1a) Sum up all numbers and
1b) Divide by 2 (store result in "halftotal").
2) Sort the data
3) Starting at the top of the sorted list, loop through the data and assign values to each subgroup
3a) Assign value to group A until the sum of group A is just less than halftotal
3b) Assign the remaining values to group B
Note that this algorithm puts the smallest numbers into group A and the largest numbers into group B. Also note that, unless the sum of groupA is exactly halftotal, then group A's sum will be smaller than group B's sum.

The main thing to change to expand this to 6 groups is to change 1b so that you divide total sum by 6 instead of 2. Note that the algorithm will still put the smallest numbers in group A, the largest numbers in group F, and the intermediate values in order from group B to group E. Also note that Groups A through E will all have sums smaller than total/6, and group F will be the group with a sum larger than total/6. This may not be the "optimal" distribution of values -- if "optimal" is even important to your application.

Before spending a lot of effort editing and debugging this code, I would suggest you consider whether or not this algorithm is appropriate for what you want to do. If you like those results, then editing this procedure should be relatively straightforward. If this is not an appropriate result, then it may take quite a bit to edit this (perhaps to the point of preferring a different starting procedure) to get what you want.

[shaclark]

Mr. Shorty,

Thanks so much for your reply and your detail. I did not feel I understood what the code was doing to expand this out, so, first, thank you sincerely for the time you took to help me better understand what's happening.

Second, you're right that it will not be ideal to have the first and last group artificially skewed smaller or larger, respectively.

Here's what is actually happening:

I've a population of 10,000 units, which belong to one of 33 categories. I need to divide those 33 categories up so that each of six teams will be responsible for as close to an equal number of units (i.e., as close to 1666) with no extreme outliers. The categories have a varying size: some as little as ten units, some as many as 500, so the ideal solution will re-test in order to come up with an optimal combination.

I did try to do my research before bothering you all... user "shg" posted what looks like a workable solution in post # 758971 but his formulae don't present the result he shows even if copied exactly as directed, so... that didn't help. I turned to the code, above, but ran into my own limitations.

Can anyone recommend a way to proceed?

Thanks,
Scott

[MrShorty]

I'm not sure what to recommend. These "resource allocation" type problems are outside of what I normally work on. I cannot readily think of a simple "edit" to the previous procedure that will do this. (I could think of an inefficient "brute force" type method that computes "subset sums" for every possible combination and then finds the "best" fit from there).

I do know that resource allocation is a common topic of study in computer science. I put "resource allocation algorithm excel" into my favorite search engine and came across several results. Among the top results:
This formula based spreadsheet + discussion: http://chandoo.org/wp/2012/10/11/for...ensics-no-031/
This Solver based template + discussion: https://www.exceldemy.com/allocating...-using-solver/

There are others out there. I wish I could help more, but I am not very familiar with this branch of programming.

[humdingaling]

please provide link to post in which you refer to
https://www.excelforum.com/excel-pro...um-groups.html
http://www.excelforum.com/excel-gene...f-numbers.html

looking at SHG post...slight error in the formula he provided
Try

Please Login or Register  to view this content.

to extend it to 6 groups simply extend the range for the Group

attached file is the same formula/method extended to 6 groups

[scottiex]

maybe this thread is the one you thought of?
https://www.excelforum.com/excel-pro...qual-sets.html

Maybe this helps.

Please Login or Register  to view this content.