acc1's blog

Dynamic Programming .. may be..
By acc1, 14 years ago, In English

I need to divide a set of players into two teams such that the team is balanced as far as possible .

Balancing is with respect to their skill values.

One of the team must have floor(n/2) players.

I initially thought it to be a NP-Complete problem , but I am now thinking that it a DP problem may be.

Can anyone tell how to solve this question.


Example:

Players: 5

Skill values:

Player 1 : 4

Player 2 : 1

Player 3 : 4

Player 4 : 56

Player 5 : 3


Optimal solution will have two teams of Total Skill values 11 and 57 respectively.


Now Constraints ( These contraints may also be helpful in solving the problems ):

Skill value of each player <= 570

Total Number of players  <  200

----------------------------------------------

Plz tell how to solve , any method You think of as the best  , plz write it .  



  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
First of all, an NP-complete problem may have a DP solution under certain constraints. In this particular one (which is NP-complete in general), suppose that you can count values possible[i][j], which is true if it is possible to take a subset of the first i players with summary skill j, and false otherwise. Then, to answer the problem you'd need to find the value of j closest to sum(skill[i])/2 for which possible[N/2][j] is true (the closer j is to the sum of skills, the more balanced your teams are). I propose you to find the recurrent relation of computing possible[i][j] yourself.
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    I believe, you meant "subset of size i", not "subset of the first i players", because otherwise possible[N/2][j] just gives info about the fact that we can or can not choose subset of first N/2 players with the given sum which is not what we need. Right?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yep, was writing something similar to your idea and got lost in between :)
      → Reply
14 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it
First idea that pops into mind - kind of knackpack:
let F(i,j,k) be true if it is possible to choose j players out of first i such that sum of their skill is k. If F(i,j,k) is true, then F(i+1,j,k) and F(i+1,j+1,k+skill(i+1)) are also true. Once you fill all the table, you can find F(n,floor(n/2), k)=true such that k is as close to sum of all skils/2.0. 
However, this method has complexity O(M*N*N*N) where M is maximum possible skill and what I've described is not fast enough to fit in 1s if it is a contest problem.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

@maksay and gojira , Thank You for your precious time . 

So, as maksay described above , it can be solved in O(M*N*N*N) time and 

O(N*N*S/2) space.

where N = no. of players.

M = Max possible skills of any particular player.

S = total_skill_sum .

----------------------------------

I need a bit faster (and if possible then , a space efficient) way of doing it.

As this was a first idea that came to maksay's mind , can anyone (incl. maksay ) improve upon it (!).

→ Reply
  • 14 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    If you need only total skills of team, then you can reduce memory to O(N*S), because when you process new player you need only in F[i][][] and F[i + 1][][].

    some idea:
    If we guess, that absolute value of skill sums of two teams in optimal solution <= M (maximal skill overall), then we can modify dp of maksay in the following way:
    f(n, first_team, diff) = true/false -- if it possible to make difference of skills equals to diff, and we choose first_team players for first team of the first n.
    In this way the complexity is O(n * n * m).
    But i'm not sure in my guess. Maybe someone can try to prove or disprove this? I'm thinking in the following way (a - is 1-indexed array of skills): 
    1) sort all skills from small to large. 
    2) for 0 players guess is right, for 2 players too, 
    3) for n player (n is even) we have next: if for (n - 2) players we can make |difference| <= M, then if difference < 0 then we add a[n] - a[n - 1] (n to first team, n - 1 to second team), if difference >= 0 then we add a[n - 1] - a[n] (n - 1 to first team, n to second team) and |difference| still <= M, so by induction it right for any n. 
    4) if n is odd, then we take solution for n - 1 and if difference(n - 1) >= 0 then add a[n] to second team (difference - a[n]), else to first team (difference + a[n]), and new |difference| will be <= a[n] and <= M.
    → Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Thank You cmd for your kind effort.

Your proof seems correct to me.

that max possible difference between two teams formed at last will be  <= M.

M = max skill value of any particular player.

Now, Can you provide a little bit more detail on how to implement your DP.

i.e. how to go about finding f(n , first_team , diff) .

maksay's dp was easier for me to implement. As it was starting from base case and kept on adding new elements ..by scanning through skills one by one.

I would like to know how to go about your DP because it has diff as last parameter , I am a bit lost.

Can anyone provide an insight.

 

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Seems to be, that my dp is wrong, because intermediate difference can be more than M. For example: skills = 5 5 4 4 4 2 - if we process players in this order, then after two steps difference will be 10 (> 5), however the resulting difference < M.
    So it dp still O(n * n * s).
    → Reply