Algorithm to partition a multiset into $K$ equal sized multisets

Question

How can I partition a multiset of integers, $A$, of size $N=MK$, into $K$ equal-sized multisets, $G_1,G_2,\ldots,G_K$, such that $\sum_i \mathrm{\lvert \min(G_i)\rvert}$ is maximized? Here, $\min(G)$ denotes the multiset consisting of a single element, the minimum element of $G$, with multiplicity equal to the element's multiplicity in $G$.

Or in simple words-

Given $N$ integers, I have to group them with each group having $M$ integers in it. Now each group has to have integers with same values so to do that we can only decrease the value of integers.

Now I want to minimize the number of those transformation.

Eg - N=5 M=5
2 2 2 2 10
We can decrease 10 to 2.
Group - (2,2,2,2,2)
No. of Transformation=1

Eg 2 - N=6 M=3
1 2 4 7 1 5
We can reduce 4 to 1 ,  5  and 7 to 2 
Groups - (1,1,1) , (2,2,2)
No. of Transformations=3

I hope this example makes it a bit more clear

 Eg - 3 : N=8
    1 2 2 5 5 6 6 1
    (a) M=2
    Groups - (1,1),(2,2),(5,5),(6,6)
    without reducing any number - optimal solution
    No. of Transformation=0
    (b) M=4
    Groups - (1,1,1,1),(5,5,5,5)
    Here all 2's were reduced to 1 and all 6's to 5 - optimal solution
    No. of Transformations=4

I first thought of Hit and Trial which will be very time consuming. Then I thought of sorting the list and then pick M elements in the list and then answer will be sum of elements that are larger than the smallest element in each group. But this is not correct approach and will often give wrong answer.

Is there an optimal and efficient way to do this and find number of transformations?

Answer 1

I would think of a somewhat greedy approach. One of your sets will include the smallest element of $A$ and clearly it should get all the copies of that element. The rest of the $M$ slots do not matter for your total score. If there are several copies of the next smallest element, they should all go in another set. If there is only one, put it in the first set so it doesn't give you a score of $1$. Look for the elements that have lots of copies and put them in a set together, then see if you can fill the set up with larger numbers. Start with the best score you can get by picking the $G_i$ of highest quantity, then see if you can fill the non-counting slots with elements higher than $G_i$. If you run into trouble, you need to choose a different set of target $G_i$