Best algorithm to generate even strong teams

Viewed 853

I got a list of players with a skill from 0-100 and a list of teams which have all their own members list.

Now I want to put the players to the teams so that teams mostly got the same size (+-1 difference is ok) and the sums of the skills should be as close at possible.

My current solution is a simple voting algorithm (teams vote players in circle, an take the next best player):

public class Teamgenerator {
    public void calcTeams(){
        List<Team> teams = new ArrayList<>();
        teams.add(new Team("Team 1"));
        teams.add(new Team("Team 2"));

        List<Player> players = new ArrayList<>();
        players.add(new Player("Player 1",25));
        players.add(new Player("Player 2",50));
        players.add(new Player("Player 3",50));
        players.add(new Player("Player 4",75));

        int nextTeam = 0;
        while (players.size() > 0) {
            int bestPlayer = findBestPlayerIndex(players);
            teams.get(nextTeam).players.add(players.get(bestPlayer));
            players.remove(bestPlayer);

            if (nextTeam < teams.size() - 1) nextTeam++;
            else nextTeam = 0;
        }

        for(Team t:teams){
            System.out.println(t.getName()+":");
            for(Player p:t.players)
                System.out.println(p.getName()+", Skill "+p.getSkill());
        }
    }


    private int findBestPlayerIndex(List<Player> players) {
        //In my real programm i have to pick the skill of a more complex player object from a DB, 
        //depending on a specific competition,  which causes i really need this index finding
        int index = -1;
        int highestSkill=-1;
        for (int i = 0; i < players.size(); i++) {
            if (players.get(i).getSkill() > highestSkill) {
                highestSkill = players.get(i).getSkill();
                index = i;
            }
        }
        return index;
    }
}

public class Team {
    private String name;
    public ArrayList<Player> players=new ArrayList<>();

    public Team(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

public class Player {
    private String name;
    private int skill=50; //From 0-100

    public Player(String name, int skill) {
        this.name = name;
        this.skill = skill;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getSkill() {
        return skill;
    }

    public void setSkill(int skill) {
        this.skill = skill;
    }   
}

The problem is that gives not the most even teams, console output is:

Team 1: Player 4, Skill 75; Player 3, Skill 50

Team 2: Player 2, Skill 50; Player 1, Skill 25

But it would be more fair if the teams are 4+1 and player 3+2. You got any idea of a more fair algorithm? Thanks for help!

1 Answers
Related