帮助数学/编码可能的组合组合总数 - C＃

Question

我有一个编码/数学问题，我需要帮助翻译成C＃。这是一款扑克筹码计算器，它可以接受BuyIn，玩家人数和每种颜色的筹码总数（有x个颜色）及其价值。

然后它显示每个人的每个可能的组合芯片等于购买。然后用户可以选择他们想要使用的芯片组分配。最好用一个简单的例子来说明。

• 买入费：$ 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 ？我需要从根本上改变我的方法methinks ...

任何人都可以让我在正确的轨道上如何解决这个请吗？伪码将起作用 - 感谢您的任何建议！

以下是我迄今为止的尝试 - 这是无望的（不会编译，只是一个例子，向您展示我的思维过程，迄今为止） - 最好不要看它，因为它可能会偏见你的解决方案..

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

输入买入费：
输入芯片类型的数目：
输入3个芯片值：
输入3倍芯片的量：
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 2

对于一些大的组合，这在有限的时间内显然是不可解的。 （这是一个NP问题）

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

此外还有一些与代码链接？这可以帮助你。 希望这会有所帮助。

Answer 3

通过种的数量递归打破问题向下芯片。

为基础的情况下，有多少种在那里进行的$ 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; 
    } 
}