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