贪心算法——找零钱

人民币有100、50、10、5、2、1、0.5、0.2、0.1等多种面额（单位为：元）。例如需补零钱68.9元，至少有以下方案： 1.1张50、1张10、1张5、3张1、1张0.5、2张0.2； 2..1张50、1张10、1张5、3张1、1张0.5、4张0.1； 3.6张10、1张5、3张1、1张0.5、2张0.2 我们要找的就是张数最少的那种方方案。 给出代码： 转换成单位为：分；便于计算。

#define MAXN 9 int parvalue[MAXN] = { 10000,5000,1000,500,200,100,50,20,10 }; int num[MAXN] = { 0 }; int exchange(int n) { int i, j; for (i=0;i<MAXN;i++) { if (n > parvalue[i]) break;//找到比n小的最大面额 } while (n>0 && i<MAXN) { if (n>= parvalue[i]) { n -= parvalue[i]; num[i]++; }else if (n<10 && n>=5) { num[MAXN - 1]++; break; } else i++; } return 0; }