硬幣更改，只是不能正確地得到它

Question

你好，我試圖創建一個algorythm，找出有多少種方式我可以得到變回。 但我只是無法得到實施權，我不斷得到4，我應該得到6，我只是不明白爲什麼。

這是我在C＃實現，它是從僞創建http://www.algorithmist.com/index.php/Coin_Change

 private static int[] S = { 1, 2, 5 }; 
     private static void Main(string[] args) 
     { 
      int amount = 7; 
      int ways = count2(amount, S.Length); 
      Console.WriteLine("Ways to make change for " + amount + " kr: " + ways.ToString()); 
      Console.ReadLine(); 
     }  
static int count2(int n, int m) 
     { 
     int[,] table = new int[n,m]; 

     for (int i = 0; i < n; i++) 
     { 
      for(int j = 0; j < m; j++) 
      { 
       // Rules 
       // 1: table[0,0] or table[0,x] = 1 
       // 2: talbe[i <= -1, x] = 0 
       // 3: table[x, j <= -1] = 0 

       int total = 0; 

       // first sub-problem 
       // count(n, m-1) 
       if (i == 0) // rule 1 
        total += 1; 
       else if (i <= -1) // rule 2 
        total += 0; 
       else if (j - 1 <= -1) 
        total += 0; 
       else 
        total += table[i, j-1]; 

       // second sub-problem 
       // count(n-S[m], m) 
       if (j - 1 <= -1) // rule 3 
        total += 0; 
       else if (i - S[j - 1] == 0) // rule 1 
        total += 1; 
       else if (i - S[j - 1] <= -1) // rule 2 
        total += 0; 
       else 
        total += table[i - S[j-1], j]; 

       table[i, j] = total; 
      } 
     } 
     return table[n-1, m-1]; 
    } 

Answer 1

這是算法的工作順序。按綠色的「播放」箭頭運行它。 http://www.exorithm.com/algorithm/view/make_change

我認爲主要問題是算法循環應該從-1開始。我認爲它會遞歸地寫得更清楚，但這是一個有趣的練習。

Answer 2

如果你解釋你的算法是如何工作的這將是有益的。當沒有評論和變量被命名只是n,m,i，這是很難理解的目的。例如，在迭代各種類型的硬幣時，您應該使用更多的描述性名稱，例如coinType。

但是，有些地方看起來對我很可疑。例如，您的變量i和j會重複範圍爲1 .. m或1 .. n的值 - 它們始終是正數。這意味着，你的規則2和3永遠不會運行：

// ... 
    else if (i <= -1)  // <- can never be 'true' 
    total += 0; 
    else if (j - 1 <= -1) // <- 'true' when 'j == 0' 
// ... 
    if (j - 1 <= -1)  // <- can never be 'true' 
// ... 

i是永遠不會小於或等於-1和j同樣。

Answer 3

一些觀察。

1）如果您將count函數從僞代碼移動到單獨的子例程中，它會使您的代碼更加簡單（並且不易出錯）。像這樣的東西（基於僞代碼從您的鏈接）

func count(table, i, j) 
    if (i == 0) 
    return 1 
    if (i < 0) 
    return 0 
    if (j <= 0 and i >= 1) 
    return 0 

    return table[i][j] 
end 

然後，你可以做

table[i][j] = count(table, i, j - 1) + count(table, i - S[j], j) 

在你的內部循環。

2）在count2中，您的第一個循環將發生n - 1次。這意味着，對於n == 1，您將不會進入循環體，並且不會找到任何解決方案。內循環相同：如果只有一枚硬幣，則不會找到任何解決方案。

Answer 4

我相信你的意思是表格[我，j]存儲的方式，以只使用硬幣{0,1,2，...，j - 1}的價值完全達到美分的數量。

本質上，while循環的內部部分是說表[i，j]應該等於達到i的值時不使用任何硬幣j的方法的數量，加上實現數值的方法的數量我使用至少一個價值S [j]的硬幣。因此，除邊界情況外，其值爲表[i，j - 1] +表[i - S [j]，j];總和的第一部分是使用沒有價值S [j]的硬幣到達我的方法的數量，第二部分是使用至少一個值S [j]的硬幣到達i的方法的數量。

嘗試改變：

 // second sub-problem 
     // count(n-S[m], m) 
     if (j - 1 <= -1) // rule 3 
      total += 0; 
     else if (i - S[j - 1] == 0) // rule 1 
      total += 1; 
     else if (i - S[j - 1] <= -1) // rule 2 
      total += 0; 
     else 
      total += table[i - S[j-1], j]; 

到：

 // second sub-problem 
     // count(n-S[m], m) 
     if (i - S[j] == 0) // rule 1 
      total += 1; 
     else if (i - S[j] < 0) // rule 2 
      total += 0; 
     else 
      total += table[i - S[j], j]; 

僅供參考，它是標準的寫類似（j < 0）而不是（j < = -1）。

Answer 5

出於絕對的深夜無聊（是的，這肯定需要精煉）......它一次使用遞歸，linq和yield，並且具有與代碼行數一樣多的括號，所以我相當不滿意它...

static IEnumerable<List<int>> GetChange(int target, IQueryable<int> coins) 
    { 
     var availableCoins = from c in coins where c <= target select c; 
     if (!availableCoins.Any()) 
     { 
      yield return new List<int>(); 
     } 
     else 
     { 
      foreach (var thisCoin in availableCoins) 
      { 
       foreach (var result in GetChange(target - thisCoin, from c in availableCoins where c <= thisCoin select c)) 
       { 
        result.Add(thisCoin); 
        yield return result; 
       } 
      } 
     } 
    }