Most optimal way of grouping sets of game characters

Question

I have been trying to solve this for two days now and have not come up with a good solution. Say if I have 8 character groups, like the following, how could I get them in teams of three so that all the characters are used up? For instance:

160 dwarves+
160 elves+
85 humans+
48 hobbits+
47 gnomes+
45 orcs+
31 wizards+
15 dragons= for a total of 591 characters.

Now I need to get each character into a team made up of three characters until all the characters are used up. For instance: 85 teams of (1 dwarf, 1 elf, and 1 human), 48 teams of (1 hobbit, 1 dwarf, 1 elf), etc. etc. until all the characters are used up. I need an equation that can be applied in a programming language where the number of each character class can change (for instance it might be 28 wizards instead of 31) and the sizes of all the team could be three or four or x. If I need to post on computer science section let me know.

So far the only way I have been able to figure it out is take the top most three classes, and make a team of the greatest number that is possible, and go down the list that way.

So with that method I would have:
85 teams of (1 dwarf, 1 elf, and 1 human) (which now leaves 75 dwarfs and elves unteamed, and 0 humans unteamed)
48 teams of (1 hobbit, 1 dwarf, 1 elf), (which now leaves 27 dwarves and elves unteamed, and 0 hobbits unteamed)
31 teams of (1 orc, 1 gnome, 1 wizard), (which now leaves 27 dwarfs, 27 elves, 16 gnomes, 14 orcs, 0 wizards unteamed)
16 teams of (1 gnome, 1 dwarf, 1 elf), (which now leaves 11 dwarfs, 11 elves, 0 gnomes, 14 orcs unteamed)
11 teams of (1 dragon, 1 orc, 1 dwarf), (which now leaves 0 dwarfs, 11 elves, 4 dragons, 3 orcs unteamed)
3 teams of (1 orc, 1 elf, 1 dragon).

So the final is an excess of 8 elves and 1 dragon that cannot be put into teams!!! I can code this method but and I realize there might be excess no matter how I do it but there has got to be a better way!

Thanks,

Paul

Answer 1

Your greedy solution of always taking the top three classes almost works; you just need to make sure that you are updating which classes really are the top three in between making each team. Here's what happens with this updated greedy algorithm (note that I'm storing them in an array of the form: $$ [Dw, El, Hu, Ho, Gn, Or, Wi, Dr] $$ but you'd probably want to use something like a priority queue):

• Step 1: $[160, 160, 85, 48, 47, 45, 31, 15]$. Make $37$ teams of $(Dw, El, Hu)$.
• Step 2: $[123, 123, 48, 48, 47, 45, 31, 15]$. Make $1$ team each of $(Dw, El, Hu)$ and $(Dw, El, Ho)$.
• Step 3: $[121, 121, 47, 47, 47, 45, 31, 15]$. Make $2$ teams each of $(Dw, El, Hu)$ and $(Dw, El, Ho)$ and $(Dw, El, Gn)$.
• Step 4: $[115, 115, 45, 45, 45, 45, 31, 15]$. Make $14$ teams each of $(Dw, El, Hu)$ and $(Dw, El, Ho)$ and $(Dw, El, Gn)$ and $(Dw, El, Or)$.
• Step 5: $[59, 59, 31, 31, 31, 31, 31, 15]$. Make $7$ teams each of $(Dw, El, Hu)$ and $(Dw, El, Ho)$ and $(Dw, El, Gn)$ and $(Dw, El, Or)$ and $(Dw, El, Wi)$.
• Step 6: $[24, 24, 24, 24, 24, 24, 24, 15]$. Make $3$ teams each of $(Dw, El, Hu)$ and $(Ho, Gn, Or)$ and $(Wi, Dw, El)$ and $(Hu, Ho, Gn)$ and $(Or, Wi, Dw)$ and $(El, Hu, Ho)$ and $(Gn, Or, Wi)$.
• Step 7: $[15, 15, 15, 15, 15, 15, 15, 15]$. Make $5$ teams each of $(Dw, El, Hu)$ and $(Ho, Gn, Or)$ and $(Wi, Dr, Dw)$ and $(El, Hu, Ho)$ and $(Gn, Or, Wi)$ and $(Dr, Dw, El)$ and $(Hu, Ho, Gn)$ and $(Or, Wi, Dr)$.
• Step 8: $[0, 0, 0, 0, 0, 0, 0, 0]$

Note that this solution was inspired from the Havel-Hakimi algorithm for showing that a degree sequence in graph theory is graphic.