Помогите с математикой / кодированием на возможных комбинациях набора, чтобы составить итог - C #

Question

У меня проблема с кодированием / математикой, и мне нужна помощь в переводе на C #.Это калькулятор покерных фишек, который учитывает BuyIn, количество игроков и общее количество фишек для каждого цвета (их количество х), а также их стоимость.

Затем отображаются все возможные комбинациифишек на человека, чтобы равняться Buy In.Затем пользователь может выбрать дистрибутив чипсета, который он хотел бы использовать.Лучше всего это проиллюстрировать на простом примере.

• BuyIn: $ 10
• Количество игроков: 1
• 10 красных фишек, стоимость $ 1
• 10 синих фишек, стоимость $ 2
• 10 зеленых фишек, стоимость 5 долларов

Итак, возможные комбинации:

R / B / G

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

и т. Д.

Я потратил много времени, пытаясь поднятьсяс алгоритмом в C # /. NET, чтобы решить это.Я натыкаюсь на переменный фактор - обычно в наборе всего 3 или 4 разных цвета фишек, но их может быть любое количество.Если у вас есть более одного игрока, то вы должны считать до TotalChips / NumberOfPlayers.

Я начал с цикла по всем фишкам, а затем с 0 до NumberOfChips для этого цвета.И это в значительной степени то, где я провел последние 4 часа ... как мне написать код для циклического прохождения x количества фишек, проверки значения суммы фишек и добавления его в коллекцию, если она равна BuyIn?Мне нужно радикально изменить мой подход ...

Может кто-нибудь подсказать мне, как решить эту проблему, пожалуйста?Псевдокод будет работать - спасибо за любой совет!

Ниже моя попытка ниже - это безнадежно (и не будет компилироваться, просто пример, чтобы показать вам мой мыслительный процесс до сих пор) - Может быть, лучше не делать этогопосмотрите на это, так как это может повлиять на ваше решение ...

   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

Вот реализация, которая считывает количество фишек, фишки (их стоимость и количество) и байин и отображает результаты в формате вашего примера. Я объяснил это в комментариях, дайте мне знать, если у вас есть какие-либо вопросы.

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);
    }
} 

Введите байин:
10
Введите количество типов фишек:
3
Введите 3 значения фишек:
1 * * +1010 2
5
Введите 3 суммы фишек:
10
10
10
10/0/0 /
8/1/0 /
6/2/0 /
5/0/1 /
4/3/0 /
3/1/1 /
2/4/0 / * * 1023 1/2/1 /
0/5/0 /
0/0/2 /

Answer 2

Рекурсивно разбить проблему на количество фишек.

В базовом случае, сколько существует способов сделать бай-ин в размере $ X с нулевыми фишками? Если X ноль, есть один путь: нет фишек. Если X больше нуля, нет способов сделать это.

Теперь нам нужно решить проблему для N видов микросхем, учитывая решение для N - 1. Мы можем взять один вид микросхем и рассмотреть каждое возможное количество этих микросхем до вступительного взноса. Например, если чип составляет 2 доллара, а бай-ин - 5 долларов, попробуйте использовать 0, 1 или 2 из них. Для каждой из этих попыток мы должны использовать только оставшиеся N - 1 фишки, чтобы составить оставшееся значение. Мы можем решить это, выполнив рекурсивный вызов, а затем добавив наш текущий чип к каждому возвращаемому решению.

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;
    }
}

Answer 3

Для некоторых больших комбинаций это, вероятно, не решаемо за конечное время (Это проблема NP)

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

Есть также ссылки с кодом? это может помочь вам. Надеюсь, это немного поможет.