I'm trying to solve this problem whole day. The result should be dynamic programming algorithm but the first thing I need is to find out recurrent function.
There is N students (N is even) in class. The class will be divided into two groups with the same number of students. Each student has it's own preference what group he want's to be a part. Group 1 and Group 2.
I have to create a DP algorithm which computes the best division of the class so the maximum possible students will be satisfied.
What I have done so far:
S|G 1|A 2|B 3|B 4|B 5|A 6|B
I rewrited the table above to this:
S|A|B 1|1|0 2|0|1 3|0|1 4|0|1 5|1|0 6|0|1
There is $1$ when student want's to be a part of the group. So we are looking for the maximal sum of 0s and 1s under condition that both groups has to have the same number of students.
But when I try to create a recursive function I can't figure out even what parameters should be there.
$OPT() = max(OPT(),OPT())$
Could you give me some hint?
I think that it could be solved another way - let's take a group A. We can consider the table as an array, where values are 0s and 1s. If a student want's to be in group A, there is 1, otherwise, there is 0. So we can sort the array and divide it into two parts. But it's not a DP approach.