#include <stdio.h>
/* Dynamic programming for making change, ver.4 */
/* to minimum the number of coins for the change. 找零錢, 用最少銅板數 */
#define MAX_CHANGE 99
#define UNIT_NAME "cent"
int nct;    /* number of coin type */
int vc[33], nc[33];    /* value of coin,  number of each coin */
int ncoins;  /* min. number of coins for the change */
void getCoinData(), printResult(), prepareChange();
int askUser(), makeChange(int);
int nmin[ MAX_CHANGE+1 ];   /* min coins for each i cents */
int left[MAX_CHANGE+1] ,right[MAX_CHANGE+1]; /* combination of money */
void countCoin(int);   /* 推算所需的各個銅板數 */
void getCoinData(){
    int i, tmp[] = { 0, 1, 5, 10, 21, 50 };
    nct = sizeof(tmp) / sizeof(int) - 1;
    for(i=1; i<= nct; ++i) vc[i] = tmp[i];
}
/**********************************************************/
int main(){
    int money, i;
    getCoinData();
    prepareChange();
    money=askUser();
    while(money > 0  && money <= MAX_CHANGE){
        ncoins = makeChange(money);
        for(i=1; i<= nct; ++i) nc[i] = 0;  /* clear coin array */
        countCoin(money);   /* nc[]: count how many coins for each coin*/
        printResult();
        money=askUser();
    }
    return 0;
}
int askUser(){
    static char tmp[99];
    printf("How much of the change? ");
    fgets(tmp, 99, stdin); 
    return (int)atol(tmp);
}
int makeChange(int m){
    return nmin[m];
}
/**********************************************************/
void prepareChange( ){ /* compute nmin[], left[], right[] */
    int i, k, m;
    nmin[0] = 0;   /* no coin needed if no money */
    for(m=1; m<= MAX_CHANGE; ++m) nmin[m] = MAX_CHANGE;
    for(i=1; i <= nct; ++i)
        nmin[ vc[i] ] = 1;   /* these all need exactly one coin */
    /******/
    for(m=2; m<= MAX_CHANGE; ++m) {
       for(i=1; i< m; ++i) { 
          k = nmin[i] + nmin[m-i];
          if( k < nmin[m] ) {  /* k=拆成 i 與 m-i 是否比較少銅板 */
             nmin[m] = k;     /* 記下最少銅板數 */
             left[m] = i;    /* .. 並記下是由 i  與 m-i 組成 */
             right[m] = m-i;
          }
       }
    }
}
/**********************************************************/
void printResult(){
    int i;
    printf("Total number of coins required: %d\n", ncoins);
    for(i=nct; i>0; --i){
        if(nc[i]){
            printf("\t%2d  x %2d %s\n", nc[i], vc[i], UNIT_NAME);
        }
    }
    printf("\n");
}
void ncAdd(m){  /* m is the value of money */
    int i;     /* 找出 nc[i] 之面額為 m 的 i */
    for(i=1; i<=nct; ++i){
       if(m == vc[i]){
           nc[i]++;
           return;
       }
    }  /* 找遍所有銅板都沒找到則表示有問題, 不該發生 */
    printf("?something Wrong! %d ?\n", m);
}
void countCoin(int m){
    int i;
    if(nmin[m]==1) { ncAdd(m); return; }
    countCoin(left[m]);
    countCoin(right[m]);
}