The coin denomination problem

I read sometime that this is a common question in interviews with Google. The problem states:

Given any set of coins, build an algorithm that returns the minimum amount of coins necessary to make up this number.

The first naive strategy one tends to follow is to use the maximim amount of the maximum valued coins in the set, and then follow with lower valued coins. This usually works with real world coin systems, with follow a pattern that makes this possible. However, the general problem is slightly more complicated. Consider the following set of coins: {1,2,5,8,10}. This set won't work with this strategy.

A better approach consists on considering the lower-valued coins not only when more higher valued coins are substracted, but on every iteration. When we are finished, we perform the same operation recursively, without using the highest-valued coin at the present recurseve call. In the example, we would take the 10-coin out, in the next recursive call, we take the 8-coin out, an so forth. Thus, we take into account all possibilities. Of course, we should track the minimum number of coins to cut the tree.

The following program implements the solution to this problem:

/* This program solves the coin denomination problem.
//
// You may redistribute this file according to the GPL terms.
// Copyright 2006 Javier Arriero Pais
*/

#include <stdio.h>
#include <stdlib.h>

#define MAXC 5
int coins[MAXC] = {1,2,5,8,10};

int amount = 13;

int numcoins (int, int);

int main (int argc, char *argv[])
{
 if (argc &gt; 1)
amount = strtol (argv[1], NULL, 10);

 printf ("Minimal number of coins: %i\n", numcoins(amount, MAXC) );

 return 0;
}


int numcoins (int amount, int maxc)
{
 int i;
 int auxamount=amount, mon=10000, auxmon=0, auxmon2;

 if (maxc&lt;=0) return 0;
 if (maxc==1) return amount;
 if (amount &lt;= 0) return 0;
 if (amount == 1) return 1;

 i=maxc-1;
 while (auxamount &gt;= coins[i]) {
auxamount-=coins[i];
auxmon2 = numcoins (auxamount, maxc-1);
auxmon++;
if (auxmon + auxmon2 &lt; mon) mon = auxmon2 + auxmon;
 }

 auxmon2 = numcoins(amount, maxc-1);

 if (auxmon2 != 0 && auxmon2 < mon)
mon = auxmon2;

 return mon;
}