Build up List from another List

Question

I've got a list of Players. Each Player has a Marketvalue. I need to build up a second list which iterates through the player list and builds up a team. The tricky thing is the new team should have at least 15 players and a maximum Marketvalue of 100 Mio +/- 1%.

Does anyone know how to do that elegantly?

    private Result<List<Player>> CreateRandomTeam(List<Player> players, int startTeamValue)
    {

        // start formation  4-4-2
        // Threshold tw 20 mio defender 40 mio Midfielder 40 Mio Striker 50 Mio
        var playerKeeperList = players.FindAll(p => p.PlayerPosition == PlayerPosition.Keeper);
        var playerDefenderList = players.FindAll(p => p.PlayerPosition == PlayerPosition.Defender);
        var playerMidfieldList = players.FindAll(p => p.PlayerPosition == PlayerPosition.Midfield);
        var playerStrikerList = players.FindAll(p => p.PlayerPosition == PlayerPosition.Striker);

        List<Player> keeperPlayers = AddRandomPlayers(playerKeeperList, 2, 0, 20000000);
        List<Player> defenderPlayers = AddRandomPlayers(playerDefenderList, 4, 0, 40000000);
        List<Player> midfieldPlayers = AddRandomPlayers(playerMidfieldList, 4, 0, 40000000);
        List<Player> strikerPlayers = AddRandomPlayers(playerStrikerList, 2, 0, 50000000);


        List<Player> team = new List<Player>();
        team.AddRange(keeperPlayers);
        team.AddRange(defenderPlayers);
        team.AddRange(midfieldPlayers);
        team.AddRange(strikerPlayers);

        var currentTeamValue = team.Sum(s => s.MarketValue);
        var budgetLeft = startTeamValue - currentTeamValue;

        players.RemoveAll(p => team.Contains(p));

        var player1 = AddRandomPlayers(players, 2, 0, budgetLeft);
        team.AddRange(player1);
        players.RemoveAll(p => player1.Contains(p));
        currentTeamValue = team.Sum(t => t.MarketValue);
        budgetLeft = startTeamValue - currentTeamValue;

        var player2 = players.Aggregate((x, y) => Math.Abs(x.MarketValue - budgetLeft) < Math.Abs(y.MarketValue - budgetLeft) ? x : y);

        team.Add(player2);
        players.Remove(player2);

        return Result<List<Player>>.Ok(team);
    }

    private static List<Player> AddRandomPlayers(List<Player> players, int playerCount, double minMarketValue, double threshold)
    {
        // TODO: AYI Implement Random TeamName assign logic
        Random rnd = new Random();
        var team = new List<Player>();
        double assignedTeamValue = 0;

        while (team.Count < playerCount)
        {
            var index = rnd.Next(players.Count);
            var player = players[index];
            if ((assignedTeamValue + player.MarketValue) <= threshold)
            {
                team.Add(player);
                players.RemoveAt(index);
                assignedTeamValue += player.MarketValue;
            }
        }

        return team;
    }`

Answer 1

This isn't really a C# question so much as an algorithm question, so there may be a better place for it. AIUI, you want to pick 15 numbers from a list, such that the total adds up to 99-101.

It's likely that there are many solutions, all equally valid.

I think you could do it like this:

1. Build a list of the 14 cheapest items.
2. Pick the highest value, so long as the remaining space is greater than the total of the 14 cheapest.
3. Repeat the above, skipping any players that won't fit.
4. Fill the remaining places with players from the 'cheapest' list.

This will probably give you a team containing the best and worst players, and one middle-ranking player that just fits.

If you want to do some more research, this sounds like a variant of the coin change problem.

Answer 2

Just to show my solution if someone need's it.

var selection = new EliteSelection();
        var crossover = new OnePointCrossover(0);
        var mutation = new UniformMutation(true);
        var fitness = new TeamFitness(players, startTeamValue);
        var chromosome = new TeamChromosome(15, players.Count);
        var population = new Population(players.Count, players.Count, chromosome);

        var ga = new GeneticAlgorithm(population, fitness, selection, crossover, mutation)
        {
            Termination = new GenerationNumberTermination(100)
        };

        ga.Start();

        var bestChromosome = ga.BestChromosome as TeamChromosome;
        var team = new List<Player>();

        if (bestChromosome != null)
        {
            for (int i = 0; i < bestChromosome.Length; i++)
            {
                team.Add(players[(int) bestChromosome.GetGene(i).Value]);
            }

            // Remove assigned player to avoid duplicate assignment
            players.RemoveAll(p => team.Contains(p));

            return Result<List<Player>>.Ok(team);
        }

        return Result<List<Player>>.Error("Chromosome was null!");

There is a fitness method which handles the logic to get the best result.

class TeamFitness : IFitness
{
    private readonly List<Player> _players;
    private readonly int _startTeamValue;
    private List<Player> _selected;

    public TeamFitness(List<Player> players, int startTeamValue)
    {
        _players = players;
        _startTeamValue = startTeamValue;
    }
    public double Evaluate(IChromosome chromosome)
    {
        double f1 = 9;
        _selected = new List<Player>();

        var indexes = new List<int>();
        foreach (var gene in chromosome.GetGenes())
        {
            indexes.Add((int)gene.Value);
            _selected.Add(_players[(int)gene.Value]);
        }

        if (indexes.Distinct().Count() < chromosome.Length)
        {
            return int.MinValue;
        }


        var sumMarketValue = _selected.Sum(s => s.MarketValue);
        var targetValue = _startTeamValue;
        if (sumMarketValue < targetValue)
        {
            f1 = targetValue - sumMarketValue;
        }else if (sumMarketValue > targetValue)
        {
            f1 = sumMarketValue - targetValue;
        }
        else
        {
            f1 = 0;
        }

        var keeperCount = _selected.Count(s => s.PlayerPosition == PlayerPosition.Keeper);
        var strikerCount = _selected.Count(s => s.PlayerPosition == PlayerPosition.Striker);
        var defCount = _selected.Count(s => s.PlayerPosition == PlayerPosition.Defender);
        var middleCount = _selected.Count(s => s.PlayerPosition == PlayerPosition.Midfield);
        var factor = 0;
        var penaltyMoney = 10000000;
        if (keeperCount > 2)
        {
            factor += (keeperCount - 2) * penaltyMoney;
        }

        if (keeperCount == 0)
        {
            factor += penaltyMoney;
        }

        if (strikerCount < 2)
        {
            factor += (2 - strikerCount) * penaltyMoney;
        }

        if (middleCount < 4)
        {
            factor += (4 - middleCount) * penaltyMoney;
        }

        if (defCount < 4)
        {
            factor += (4 - defCount) * penaltyMoney;
        }


        return 1.0 - (f1 + factor);
    }
}