一道面试题

假设有一种货币有C1,C2,C3....Cn种面值（分），写一个程序，实现找零钱用的硬币数量最少。注：比如应该摘8分钱那么结果就是1分，2分，5分

解决方案 »

  1.   

    我的想法：设现在金额为m我们从最大的面值金额找起 m = Cn + (m-Cn);接下来我们继续找m-Cn，仍然从最大面值金额找起，m-Cn = Cn + (m-Cn-Cn),这里得判断，m-Cn与Cn的大小，如果m-Cn < Cn ,那么自然从C(n-1)找起，如此递归，但是我没有想到结束递归的条件呢！！呵呵
      

  2.   

    答：设现在金额为m，则：m整除最大的面值Cn,商就是Cn的个数，然后余数=>m,继续:整除次最大的面值Cn-1,
    商就是Cn的个数，然后余数=>m,继续 ...直到C1(当然：可进一步优化：不一定每一个面值Ci都要除）
      

  3.   

    背包算法才是正解，由大到小for循环不能得到最优解