幫助數學/編碼可能的組合組合總數 - 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; 
    } 
}