.
算法设计与分析课程设计
一、 课程题目
零钱问题贪心算法实现
二、课程摘要
1）题目描述
使用贪心算法设计思想设计算法实现找零钱问题。
例题13-4 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。
1）在给定钱币面值的前提下，实现找回尽量少硬币的输出方案 2）分析算法性能 2）贪心算法简述
在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。
三、课程引言
首先，证明找零钱问题的贪婪算法总能产生具有最少硬币数的零钱。 证明：（1）找零钱问题的最优解必以一个贪心选择开始，当总金额为N,硬币面值为25，10，5，1时。
设最大容许的硬币面值为m,最优解必包含一个面值为m的硬币: 设A是一个最优解，且A中的第i个硬币面值为f(i)。 当f(1)=m（此处为25）,得证；
若f(1) A中若不存在Ak使f(k)=m,则必有n个硬币(n>1)之和 （2）已证明A是最优解且A始于贪心选择。则A'=A-{1}是找出总额为M-f(1)零钱的一个最优解。若有解B'使找零钱数少于A',则将m加入B'中，得到一个原问题的最优解且优于A，这与A是最优解矛盾。可见每步所作的贪心选择都将原问题简化为一个规模 ;. . 较小的子问题，对贪心步数归纳,得证此问题贪心必有最优解。 四、课程正文 1） 算法设计、分析 解决找零钱问题用动态规划来解，归结到动态规划上面就变成了无限背包问题（因为收银台的硬币默认是无穷的，但一种改进版本可以考察有限硬币的情况）。区别在于，现在我们需要求一个最少的硬币数而不是最大值。但是选择的情况也是相同的，即每次选择都可以选择任何一种硬币。 首先，找零钱问题具有最优子结构性质： 兑换零钱问题的最优子结构表述：对于任意需要找的钱数j，一个利用T[n]中的n个不同面值钱币进行兑换零钱的最佳方案为P(T(1),j)，P(T(2),j),...,P(T(n),j)，即此时的最少钱 C(n,j)??P(T(k),j)k?1n币个数，则P(T(2),j),...,P(T(n),j)一定是利用T[n]中n个不同的面值钱 币对钱数j=j-P(T(1),j)* T(1)进行兑换零钱的最佳方案。 其次，找零钱问题具有重叠于问题性质： a)当n=1时，即只能用一种钱币兑换零钱，钱币的面值为T[0]，有 j%T[1]?0? j/T[1]j%T[1]?0 b)当n>1时， 若j>T[n],即第n种钱币面值比所兑换零钱数小,因此有 C(1,j)??C(n,j)?min{C(n,j?T[k])?1}1?k?n。当k为 k0(1?i?n)时，C(n,j)达到最小值，有 P(T(k0),j)=P(T( k0)，j-T( k0))+1 若j=T[n]，即用n种钱币兑换零钱，第n种钱币面值与兑换零钱数j相等，此时有C(n,j)=C(n,T[n])=1； P(i,j)?P(i,T[n])??1,i?T[n]0,i?T[n] 若j C(1,j)?? C(i,j)??C(i-1,j) 0?j?T[i]; min(C(i-1,j),C(i,j-T[i])?1) j?T[i] （2） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。 2O(n)； 答：算法的时间复杂度主要取决于程序的两个循环，所以算法的时间复杂度为 算法执行过程中引入了一个二维数组，随着输入规模的增大，所需要的空间复杂度为： O(n2) ;. . 考虑例1 3 - 4的找零钱问题，假设售货员只有有限的2 5美分， 1 0美分， 5美分和1美分的硬币，给出一种找零钱的贪婪算法。这种方法总能找出具有最少硬币数的零钱吗？证明结论。 源代码如下： # include const int M=100; //小孩给的钱数 const int twentyfnum=3; //25美分硬币 const int tennum=3; //10美分硬币 const int fivenum=3; //5美分硬币 const int onenum=3; //1美分硬币 const int tnum=twentyfnum+tennum+fivenum+onenum; //硬币的总数量 int main() { int a[tnum],i; //数组初始化,数组中的元素由大到小排列 int *p=a; for(i=0;i cout<<\找钱方案:\ cout<<\美分:\枚,\美分:\枚,\美分:\枚,\美分:\枚\ } else cout<<\零钱不够\ system(\ ;.