tsaiwn dynamic % cat -n coin2.c
     1  #include <stdio.h>
     2  /* Dynamic programming for making change, ver.1 */
     3  int nct;   /* number of coin type */
     4  int vct[33], nc[33];    /* value of coin,  number of each coin */
     5  int ncoins;  /* min. number of coins for the change */
     6  void getCoinData(), printResult();
     7  int ask(), makeChange(int);
     8  int nmin[100];   /* min coins for each i cents */
     9  int imax=0;
    10  int main(){
    11      int money, i;
    12      getCoinData();
    13      money=ask();
    14      while(money > 0){
    15          imax=0;
    16          for(i=1; i<=money; ++i) nmin[i] = money;
    17          for(i=1; i<= nct; ++i) nc[i] = 0;  ncoins=0; /* clear */
    18          ncoins = makeChange(money);
    19          printResult();
    20          money=ask();
    21      }
    22      return 0;
    23  }
    24  void getCoinData(){
    25      int i, tmp[] = { 0, 1, 5, 10, 21, 50 };
    26      nct = sizeof(tmp) / sizeof(int) - 1;
    27      for(i=1; i<= nct; ++i) {
    28         vct[i] = tmp[i];
    29      }
    30  }
    31  int ask(){
    32      char tmp[99];
    33      printf("How much of the change? ");
    34      gets(tmp); 
    35      return (int)atol(tmp);
    36  }
    37  int makeChange(int m){
    38      int i, k;
    39      for(i=1; i <= nct; ++i){
    40         if(m == vct[i]) return 1;
    41      }
    42      if(m <= imax) return nmin[m];   /* Remove this line and try again ! */
    43      for(i=1; i< m; ++i) {
    44         k = makeChange(i) + makeChange(m-i);
    45         if( k < nmin[m] ) nmin[m] = k;
    46         if(i>imax) imax = i;
    47      }
    48      return nmin[m];
    49  }
    50  void printResult(){
    51      int i;
    52      printf("Total number of coins required: %d\n", ncoins);
    53      for(i=nct; i>0; --i){
    54          if(nc[i]){
    55              printf("\t%d  x %2d\n", nc[i], vct[i]);
    56          }
    57      }
    58      printf("\n");
    59  }
tsaiwn dynamic % gcc coin2.c
tsaiwn dynamic % ./a.out
warning: this program uses gets(), which is unsafe.
How much of the change? 2
Total number of coins required: 2

How much of the change? 63
Total number of coins required: 3

How much of the change? 65
Total number of coins required: 3

How much of the change? 50
Total number of coins required: 1

How much of the change? 55
Total number of coins required: 2

How much of the change? 0
tsaiwn dynamic %