算法设计吧 关注:332贴子:101
  • 1回复贴,共1

一个问题:贪心算法

只看楼主收藏回复

考虑下面的用最少硬币个数找出n分钱的问题。
(1)当使用2角5分,1角,5分和1分四种硬币面值时,设计一个找n分钱的贪心算法,并证明算法能产生最优解。
(2)假设可使用的硬币面值是c0,c1,……,ck,其中c是一正整数且c>1,k≥1。证明在这种情况下,贪心算法总能产生最优解。
(3)给出一个贪心算法不能产生最优解的硬币面值集合。


1楼2005-11-04 13:13回复
    • 211.71.15.*
    {30 10 1} 求25的最少硬币数


    2楼2006-06-02 20:07
    回复