Смена монеты, просто не могу понять это правильно

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

Из-за чистой ночной скуки (и да, это определенно потребует уточнения) ... Он использует рекурсию, 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;
                }
            }
        }
    }

Answer 2

Вот алгоритм в рабочем состоянии.Нажмите зеленую стрелку «играть», чтобы запустить его.http://www.exorithm.com/algorithm/view/make_change

Я думаю, что основной проблемой было то, что циклы алгоритма должны начинаться с -1.Я думаю, что было бы гораздо яснее написать рекурсивно, но это было забавное упражнение.

Answer 3

Было бы полезно, если бы вы объяснили, как должен работать ваш алгоритм.Когда нет комментариев, а переменные называются просто 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 4

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

По сути, внутренняя часть цикла while говорит, что таблица [i, j] должна равняться числу способов достижения значения i без использования какой-либо монеты j, плюс количество способов достижения значенияя использую хотя бы одну монету достоинством S [j].Следовательно, за исключением граничных случаев, значение равно table [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];

К вашему сведению, обычно пишется что-то вроде (j <0), а не (j <= -1). </p>

Answer 5

Некоторые наблюдения.

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 вы не войдете в тело цикла и не найдете никаких решений. То же самое для внутреннего цикла: если есть только одна монета, вы не найдете никаких решений.