Help with maths/coding on possible combinations of a set to make up a total - C#

Question

I have a coding/maths problem that I need help translating into C#. It's a poker chip calculator that takes in the BuyIn, the number of players and the total amount of chips for each colour (there are x amount of colours) and their value.

It then shows you every possible combination of chips per person to equal the Buy In. The user can then pick the chipset distribution they would like to use. It's best illustrated with a simple example.

• BuyIn: $10
• Number of Players: 1
• 10 Red Chips, $1 value
• 10 Blue Chips, $2 value
• 10 Green Chips, $5 value

So, the possible combinations are:

R/B/G

• 10/0/0
• 8/1/0
• 6/2/0
• 5/0/1
• 4/3/0
• 2/4/0
• 1/2/1

etc.

I have spent a lot of time trying to come up with an algorithm in C#/.NET to work this out. I am stumbling on the variable factor - there's usually only 3 or 4 different chips colours in a set, but there could be any amount. If you have more than one player than you have to count up until TotalChips / NumberOfPlayers.

I started off with a loop through all the chips and then looping from 0 up to NumberOfChips for that colour. And this is pretty much where I have spent the last 4 hours... how do I write the code to loop through x amount of chips and check the value of the sum of the chips and add it to a collection if it equals the BuyIn? I need to change my approach radically methinks...

Can anyone put me on the right track on how to solve this please? Pseudo code would work - thank you for any advice!

The below is my attempt so far - it's hopeless (and wont compile, just an example to show you my thought process so far) - Might be better not to look at it as it might biased you on a solution...

   private void SplitChips(List<ChipSuggestion> suggestions)
    {

        decimal valueRequired = (decimal)txtBuyIn.Value;
        decimal checkTotal = 0;
        ChipSuggestion suggestion;

        //loop through each colour
        foreach (Chip chip in (PagedCollectionView)gridChips.ItemsSource)
        {
                //for each value, loop through them all again
                foreach (Chip currentChip in (PagedCollectionView)gridChips.ItemsSource)
                {
                    //start at 0 and go all the way up
                    for (int i = 0; i < chip.TotalChipsInChipset; i++)
                    {
                        checkTotal = currentChip.ChipValue * i;

                        //if it is greater than than ignore and stop
                        if (checkTotal > valueRequired)
                        {
                            break;
                        }
                        else
                        {
                            //if it is equal to then this is a match
                            if (checkTotal == valueRequired)
                            {
                                suggestion = new ChipSuggestion();
                                suggestion.SuggestionName = "Suggestion";

                                chipRed.NumberPerPlayer = i;
                                suggestion.Chips.Add(chipRed);

                                chipBlue.NumberPerPlayer = y;
                                suggestion.Chips.Add(chipBlue);

                                chipGreen.NumberPerPlayer = 0;
                                suggestion.Chips.Add(chipGreen);

                                //add this to the Suggestion
                                suggestions.Add(suggestion);
                                break;
                            }


                    }
                }
            }
        }
    }

Answer 1

For some large combinations this is propably not solvable in finite time. (It is a NP problem)

http://en.wikipedia.org/wiki/Knapsack_problem

There are also links with Code? that could help you. Hope this helps a bit.

Answer 2

Here's an implementation that reads the number of chips, the chips (their worth and amount) and the buyin and displays the results in your example format. I have explained it through comments, let me know if you have any questions.

class Test
{
    static int buyIn; 
    static int numChips;
    static List<int> chips = new List<int>(); // chips[i] = value of chips of color i
    static List<int> amountOfChips = new List<int>(); // amountOfChips[i] = number of chips of color i

    static void generateSolutions(int sum, int[] solutions, int last)
    {
        if (sum > buyIn) // our sum is too big, return
            return;

        if (sum == buyIn) // our sum is just right, print the solution
        {
            for (int i = 0; i < chips.Count; ++i)
                Console.Write("{0}/", solutions[i]);
            Console.WriteLine();

            return; // and return
        }

        for (int i = last; i < chips.Count; ++i) // try adding another chip with the same value as the one added at the last step. 
                                                 // this ensures that no duplicate solutions will be generated, since we impose an order of generation
            if (amountOfChips[i] != 0)
            {
                --amountOfChips[i]; // decrease the amount of chips
                ++solutions[i]; // increase the number of times chip i has been used

                generateSolutions(sum + chips[i], solutions, i); // recursive call

                ++amountOfChips[i]; // (one of) chip i is no longer used
                --solutions[i]; // so it's no longer part of the solution either
            }
    }

    static void Main()
    {
        Console.WriteLine("Enter the buyin:");
        buyIn = int.Parse(Console.ReadLine());
        Console.WriteLine("Enter the number of chips types:");
        numChips = int.Parse(Console.ReadLine());
        Console.WriteLine("Enter {0} chips values:", numChips);
        for (int i = 0; i < numChips; ++i)
            chips.Add(int.Parse(Console.ReadLine()));

        Console.WriteLine("Enter {0} chips amounts:", numChips);
        for (int i = 0; i < numChips; ++i)
            amountOfChips.Add(int.Parse(Console.ReadLine()));

        int[] solutions = new int[numChips];

        generateSolutions(0, solutions, 0);
    }
} 

Enter the buyin:
10
Enter the number of chips types:
3
Enter 3 chips values:
1
2
5
Enter 3 chips amounts:
10
10
10
10/0/0/
8/1/0/
6/2/0/
5/0/1/
4/3/0/
3/1/1/
2/4/0/
1/2/1/
0/5/0/
0/0/2/

Answer 3

Break the problem down recursively by the number of kinds of chips.

For the base case, how many ways are there to make an $X buy-in with zero chips? If X is zero, there is one way: no chips. If X is more than zero, there are no ways to do it.

Now we need to solve the problem for N kinds of chips, given the solution for N - 1. We can take one kind of chip, and consider every possible number of that chip up to the buy-in. For example, if the chip is $2, and the buy-in is $5, try using 0, 1, or 2 of them. For each of these tries, we have to use only the remaining N - 1 chips to make up the remaining value. We can solve that by doing a recursive call, and then adding our current chip to each solution it returns.

private static IEnumerable<IEnumerable<Tuple<Chip, int>>> GetAllChipSuggestions(List<Chip> chips, int players, int totalValue)
{
    return GetAllChipSuggestions(chips, players, totalValue, 0);
}

private static IEnumerable<IEnumerable<Tuple<Chip, int>>> GetAllChipSuggestions(List<Chip> chips, int players, int totalValue, int firstChipIndex)
{
    if (firstChipIndex == chips.Count)
    {
        // Base case: we have no chip types remaining
        if (totalValue == 0)
        {
            // One way to make 0 with no chip types
            return new[] { Enumerable.Empty<Tuple<Chip, int>>() };
        }
        else
        {
            // No ways to make more than 0 with no chip types
            return Enumerable.Empty<IEnumerable<Tuple<Chip, int>>>();
        }
    }
    else
    {
        // Recursive case: try each possible number of this chip type
        var allSuggestions = new List<IEnumerable<Tuple<Chip, int>>>();
        var currentChip = chips[firstChipIndex];
        var maxChips = Math.Min(currentChip.TotalChipsInChipset / players, totalValue / currentChip.ChipValue);
        for (var chipCount = 0; chipCount <= maxChips; chipCount++)
        {
            var currentChipSuggestion = new[] { Tuple.Create(currentChip, chipCount) };
            var remainingValue = totalValue - currentChip.ChipValue * chipCount;
            // Get all combinations of chips after this one that make up the rest of the value
            foreach (var suggestion in GetAllChipSuggestions(chips, players, remainingValue, firstChipIndex + 1))
            {
                allSuggestions.Add(suggestion.Concat(currentChipSuggestion));
            }
        }
        return allSuggestions;
    }
}