Coin Change, just can't get it right

Question

Hello i'm trying to create an algorythm that finds out how many ways i can get change back. But i just can't get the implemtation right, i keep getting 4 where i should get 6 and i just can't see why.

This is my implementation in C#, it is create from the pseudocode from 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

It would be useful if you explained how is your algorithm supposed to work. When there are no comments and variables are named just n, m, i, it is quite difficult to understand the purpose. You should use more descriptive names such as coinType when iterating over various types of coins, for example.

However, there are some places that look quite suspicious to me. For example, your variables i and j iterate over values in range 1 .. m or 1 .. n - they are always going to be positive. This means that your rules 2 and 3 can never run:

// ...
  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 is never going to be smaller than or equal to -1 and j likewise.

Answer 2

Some observations.

1) It would make your code much simpler (and less error prone) if you move count function from pseudo-code into a separate subroutine. Something like this (based on pseudo-code from your link)

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

Then you can just do

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

in your inner loop.

2) In count2, your first loop will occur n - 1 times. It means, that for n == 1 you won't enter loop body and won't find any solutions. Same for the inner loop: if there's only one coin, you won't find any solutions.

Answer 3

I believe you mean for table[i, j] to store the number of ways to achieve a value of exactly i cents using only coins {0, 1, 2,..., j - 1}.

Essentially, the inner portion of the while loop is saying that table[i, j] should equal the number of ways of reaching a value of i without using any of coin j, plus the number of ways of achieving a value of i using at least one coin of value S[j]. Hence, except for border cases, the value is table[i, j - 1] + table[i - S[j], j]; the first part of the sum is the number of ways to reach i using no coins of value S[j], and the second part is the number of ways to reach i using at least one coin of value S[j].

Try changing:

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

to:

        // 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, it is standard to write something like (j < 0) rather than (j <= -1).

Answer 4

Out of sheer late-night boredom (and yes, this would definitely need refining)... It uses recursion, linq and yield all at once and has as many braces as it does lines of code, so I'm quite perversely pleased with it...

    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 5

Here's the algorithm in working order. Press the green "play" arrow to run it. http://www.exorithm.com/algorithm/view/make_change

I think the major problem was the algorithm loops should start at -1. I think it would be much clearer written recursively, but it was a fun exercise.