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 .

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 tosum(skill[i])/2for whichpossible[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.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?@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 (!).

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.