Dividing to groups based on preferences using dynamic programming

0
votes

I need a help to design an algoritm which would divide N students to two groups based on their preferences (preference of one group, both or none) so that we match their preferences as much as we can and they are divided equally to both of the groups. I should get O(N^3) using dynamic programming.

So I thought that the algorithm should iterate through N/2 students and choose their preference, the rest is done. Now it depends on the order of choosing this N/2 students, but I don't know if this is a good way. If someone could give me a hint, thanks.

2
algorithmdynamic-programming
I believe there's an O(N) greedy algorithm for this problem: assign students to a group based on their preferences (if they have a preference for one or the other, but not both or neither) until you run out of space in a group or you run out of students with a preference. Then assign everyone else to whatever space is left. I claim that gives an optimal solution in O(N) time and space. If you must use dynamic programming, you must, I suppose, but O(N^3) is really over the top. - Edward Doolittle

2 Answers

1
votes

I should get O(N^3) using dynamic programming.

Overkill. Simply pick up the student with the strongest preference and put him into the group he wants to be in. Repeat until at least one group has reached N/2 students. Sorting the students by strength of preference at the outset is O(N log N), the rest is O(N).

If the students don't even have preference strengths (we try to satisfy the greatest number of them), then it can be done in O(N) total time.

1
votes

This sound very similar to knapsack problem. For your case, I would suppose the following dynamic programming solution.

For each solution (i.e. assignment of students to groups) let us define its "cost" to be the number of missed preferences. (If preferences also have weights, you can also account for them in definition of "cost".)

Now we'll have ans[i][j] to be the optimal cost of assigning the first i students into groups so that the first group has j students (and the second therefore has i-j). We will populate the ans array using dynamics programming. For each i and j consider two cases: you put ith student to first group or to second.

For the first case, the cost will be (cost of putting i-th student to group 1)+ans[i-1][j-1], becase after you put ith student to group 1, you have to assign i-1 students to groups so that 1st group has j-1 students.

For the second case, the cost similarly will be (cost of putting i-th student to group 2)+ans[i-1][j].

So the resulting DP formula is

ans[i][j]=min(cost[i][1]+ans[i-1][j-1], cost[i][2]+ans[i-1][j])

In case j=0 only the second term remains, in case i=j only the first.

This will be not O(N^3), but O(N^2) solution.