Изменение монеты, просто не получается это правильно

Question

Привет, я пытаюсь создать алгоритм, который узнает, как много способов получить обратно. Но я просто не могу получить правку, я продолжаю получать 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

Вот алгоритм в рабочем состоянии. Нажмите зеленую стрелку «play», чтобы запустить ее. 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

Я считаю, что вы имеете в виду таблицу [i, j] для хранения количества способов достижения значения точно в центах, используя только монеты {0, 1, 2, ..., j - 1}.

По существу, внутренняя часть цикла while говорит, что таблица [i, j] должна равняться количеству способов достижения значения i без использования какой-либо из монет j, плюс количество способов достижения значения из i использую хотя бы одну монету S [j]. Следовательно, за исключением случаев с границами, значение равно таблице [i, j - 1] + table [i - S [j], j]; первая часть суммы - это количество способов достижения i без использования монет со значением S [j], а вторая часть - это количество способов достижения i, используя хотя бы одну монету S [j].

Попробуйте изменить:

 // 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]; 

FYI, это стандарт, чтобы написать что-то вроде (к < 0), а не (к < = -1).

Answer 5

Из-за чистой ночной скуки (и да, это определенно нуждается в уточнении) ... Он использует рекурсию, linq и дает все сразу и имеет столько скобок, что и строки кода, поэтому я довольно извращенно это ...

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