This is a classical problem of Computer Science: it’s used to study both Greedy and Dynamic Programming algorithmic techniques.

Coins
I hate having my pocket full of copper!!! -_-

Definition

Given:

  • A set of n Denominations D[0...n-1] in ascending order, representing a Monetary Coin System
  • An money amount A, as input

calculate a solution:

  • S[0...n-1], with 0 <= S[i] <= (A/S[i]) and 0 < i < n-1

where:

  • A = Sum[i=0 -> n-1] { D[i] * S[i] }
  • Min{ Sum[i=0 -> n-1] { S[i] } }

In other words

Find the smallest amount of coins to make the given amount.

First, the Greedy solution

The Greedy approach is as expected: tries to take as much largest coins as possible. Nothing fancy.

change_coins_greedy(D[], A):
   init S[n]
   i = n-1
   // Pick as much largest coins as possible
   while ( A > 0 ) do:
      S[i] = A / D[i]
      A = A - S[i] * D[i]
      i = i - 1
   endwhile

   // Set to '0' the result for all the other coins
   while ( i >= 0 ) do:
      S[i] = 0
      i = i - 1
   endwhile

This algorithm, of time complexity O(A), doesn’t work for some (rare) situations.

When Greedy is not enough

The Greedy algorithm doesn’t work for Denominations where if 2 denominations D[i] and D[j] exists with:

  • i < j
  • D[i] < D[j]
  • 2 * D[i] > D[j]

For example, taken D = {1, 10, 30, 40} and amount A = 63, the Greedy algorithm will build a solution S = {3, 2, 0, 1}, that is sub-optimal. The optimal solution in this case is S = {3, 0, 2, 0}.
UPDATE: In the comments Vincenzo gives an example where this condition doesn’t still stand but the Greedy Algorithm still produces the best solution.

Dynamically Programmed Solution

In real life the Greedy algorithm should be always enough: I couldn’t find any money system that has the problem described above. And, indeed, the Greedy approach is what every human being “normally” applies when changing money.

But we are Comp-Sci, and we need to find a better solution ;-) – a Dynamically Programmed one.

Given the function M[j], that is the minimum number of coins to make the amount ‘j’, it looks like:

  • M[A] = min[i = 0 -> n-1] { M[ A - D[i] ] +1 , M[A] }

Here is the code:

unsigned int* change_coins_dynpro(unsigned short int D[],
    unsigned int D_size, unsigned int amount) {
    // Min. num. of coins for the given 'amount'
    unsigned int min_num_coins[amount], cur_min_num_coins;
    // Biggest coin used for the given 'amount'
    unsigned int biggest_coin_at[amount], cur_biggest_coin_at;

    unsigned int i, j;
    unsigned int* solution = NULL;

    // Ensure the Denomination System can represent any value
    if ( D[0] != 1 ) return NULL;

    // Initialize the solution array to Zero
    solution = (unsigned int*)calloc(D_size, sizeof(unsigned int));
    if ( NULL == solution ) {
        return NULL;
    }

    // Amount '0' requires '0' coins
    min_num_coins[0] = 0;
    biggest_coin_at[0] = 0;

    // For Amounts from '1' to 'amount'
    for ( i = 1; i <= amount; ++i ) {
        // Start taking 'D[0]' 'i-times'
        cur_min_num_coins = (i / D[0]);
        cur_biggest_coin_at = 0;

        // For coins from 'D[1]' to 'D[D_size -1]'
        for ( j = 1; j < D_size; ++j ) {
            // If 'D[j]' minimizes the num. of coins to take for amount 'i'
            if ( (i >= D[j]) && (cur_min_num_coins >= (min_num_coins[ i - D[j] ] +1)) ) {
                cur_min_num_coins = min_num_coins[ i - D[j] ] +1;
                cur_biggest_coin_at = j;
            }
        }

        // Store the minimum just found
        min_num_coins[i] = cur_min_num_coins;
        biggest_coin_at[i] = cur_biggest_coin_at;
    }

    // Let's build the solution array
    while ( amount > 0 ) {
        cur_biggest_coin_at = biggest_coin_at[amount];

        solution[ cur_biggest_coin_at ] += 1; // Add '1' of this coin to the solution
        amount -= D[cur_biggest_coin_at]; // Amount left when picking this coin
    }

    return solution;
}

Time complexity for this algorithm is O( Amount * num_of_denominations ).
Pretty heavy algorithm, but do you want to compare with the satisfaction of carrying the minimum amount of coins with you? :P