2
$\begingroup$

Say I am given eight numbers: 10, 8, 8, 7, 6. 5, 5, 4

I am told to divide the group of numbers in to two different groups, four numbers each. What formula or method is there for running every possible combination of numbers possible, and in the end output two groups who's numbers' sum is even or as close as possible.

I am looking for an algorithm for an Android application I am developing. The user inputs the names and skill of each player playing in a game of the users choice. The application will read the inputs and list the best combination of players so that the teams are as fair as possible for the given skill levels. Please let me know if you have any questions or need any more information. Thank you.

  • 0
    Is there a limit to the number of players? What about the skill rating values?2012-04-30
  • 0
    Range of number of players: 4 to 8, Range of skill: 0 to 10.2012-04-30
  • 3
    If I am not mistaken this is related to the knapsack problem. http://en.wikipedia.org/wiki/Knapsack_problem and thus NP-complete. A lot of algorithms give decent results though and with a small enough set (8players?) you could even try every reasonable possibility by brute force.2012-04-30
  • 0
    Thank you for the link to the Knapsack Problem, I have never heard of that. Do you have any idea how I could come up with a set formula for this? Since this will be applied to a computer program, I cannot sit and manually work each scenario out on paper.2012-04-30
  • 0
    Also lookup subset sum problem.2012-04-30
  • 0
    Each team has to be of 4 players? if not you can use the algorithm describe on video 7 [here](http://people.csail.mit.edu/bdean/6.046/dp/)..2012-05-04

1 Answers 1