0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Are you sure you need all this? If you have two groups and preferences and groups are half N big, it is sufficient to apply the smaller group of students according to preference and pick the rest at random. I mean there are no constraints and no obvious reason for DP or reccurence, also objective is vague, why we sum 0? $\endgroup$ – Evil Jun 6 '16 at 17:00
  • $\begingroup$ I need to be DP because it's practise in our book, I study DP right now. I was thinking about sum because if student is not satisfied, it's 0 , otherwise 1 so the bigger sum the more satisfied students. $\endgroup$ – Milano Jun 6 '16 at 17:05
  • $\begingroup$ So if your parameter is passed as number of satisfied students, starting with 0, and then you apply the maximum found to the function $acc += max(OPT(A), OPT(B))$ and return $acc$ afterwards, which is the number of satisfied studends it seems ok? Also this would very naively and redundantly execute OPT function, so DP will speedup this excersise, right? $\endgroup$ – Evil Jun 6 '16 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.