证明这个算法具有贪心选择性质？

有硬币面值25分，10分，5分，1分。
要找的硬币数目最少。
找零钱时，从大往小找。
如，67分，
25*2+10+5+1*2，
此种找法最优。
要怎么证明这种算法具有贪心选择性质？？？？

解决方案 »

  1.   

    用反证法，如果不用最大的找，用比她小的，那么硬币数量必定比她多（面值小，数量要多）
      

  2.   

    这个就是贪婪算法啊，什么叫“证明”？
    而且这种算法不是最优
    比如说对于面值 15 10 1，
    当要20分时
    按照贪婪算法：15 + 1×5
    数目为6
    而最优解应该是：10×2
    数目为2
      

  3.   

    我问题本身的特性决定了可以用贪心算法呀，也就是硬币面值组合的特殊性。可我不知道要如何分析它的贪心选择性质？？？
      

  4.   

    老大你说的贪心是指数量？说清楚
      

  5.   

    这个本身就满足贪心算法的条件，
    不需要证明啊