tsaiwn dynamic % cat -n coin3.c
     1  #include <stdio.h>
     2  #define MAX_CHANGE 99
     3  /* Dynamic programming for making change, ver.2 */
     4  int nct;   /* number of coin type */
     5  int vct[33], nc[33];    /* value of coin,  number of each coin */
     6  int ncoins;  /* min. number of coins for the change */
     7  void getCoinData(), printResult(), prepareChange();
     8  int ask(), makeChange(int);
     9  int nmin[ MAX_CHANGE+1 ];   /* min coins for each i cents */
    10  int imax=0;
    11  int main(){
    12      int money, i;
    13      getCoinData();
    14      prepareChange();
    15      money=ask();
    16      while(money > 0){
    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      return nmin[m];
    39  }
    40  void prepareChange( ){
    41      int i, k, m;
    42      nmin[0] = 0;
    43      for(m=1; m<= MAX_CHANGE; ++m) nmin[m] = MAX_CHANGE;
    44      for(i=1; i <= nct; ++i)
    45          nmin[ vct[i] ] = 1;   /* exactly one coin */
    46      /******/
    47      for(m=2; m<= MAX_CHANGE; ++m) {
    48         for(i=1; i< m; ++i) {
    49            k = nmin[i] + nmin[m-i];
    50            if( k < nmin[m] ) nmin[m] = k;
    51         }
    52      }
    53  }
    54  void printResult(){
    55      int i;
    56      printf("Total number of coins required: %d\n", ncoins);
    57      for(i=nct; i>0; --i){
    58          if(nc[i]){
    59              printf("\t%d  x %2d\n", nc[i], vct[i]);
    60          }
    61      }
    62      printf("\n");
    63  }
tsaiwn dynamic % exit