一、 课程题目。
零钱问题贪心算法实现。
二、课程摘要。
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-是找出总额为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)，即此时的最少钱币个数，则p(t(2),j),.
p(t(n),j)一定是利用t[n]中n个不同的面值钱币对钱数j=j-p(t(1),j)* t(1)进行兑换零钱的最佳方案。
其次，找零钱问题具有重叠于问题性质：
a)当n=1时，即只能用一种钱币兑换零钱，钱币的面值为t[0]，有。
b)当n>1时，若j>t[n],即第n种钱币面值比所兑换零钱数小，因此有。当k为时，c(n,j)达到最小值，有p(t(k0),j)=p(t()，j-t())1
若j=t[n]，即用n种钱币兑换零钱，第n种钱币面值与兑换零钱数j相等，此时有c(n,j)=c(n,t[n])=1；
若j从以上讨论可知该问题具有重叠子问题性质。
1） 根据分析建立正确的递归关系。
答： 2） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。
答：算法的时间复杂度主要取决于程序的两个循环，所以算法的时间复杂度为；算法执行过程中引入了一个二维数组，随着输入规模的增大，所需要的空间复杂度为：
考虑例1 3 - 4的找零钱问题，假设售货员只有有限的2 5美分， 1 0美分， 5美分和1美分的硬币，给出一种找零钱的贪婪算法。这种方法总能找出具有最少硬币数的零钱吗？证明结论。
源**如下：
# include
using namespace std;
const int c=33;
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 for(i=0;i for(i=0;i for(i=0;i bool b[tnum];
q,int n,int c);
if(findmoney(a,b,tnum,m-c))
int c[4]=;存放应找个各面值硬币的数量
bool findmoney(int *p,bool *
cout<<"找钱方案：" else cout<<"零钱不够"; system("pause"); return 0; bool findmoney(int *p,bool *q,int n,int c) for(int i=0;i if(p[i]<=c&&c!=0) if(c==0) return true; else return false; 在此程序中，程序没有实现输入和输出的模块，但是具有了找零钱问题的贪心算法解决模块，所以需要在此程序的基础上进一步优化，改进后的**如下： #include using namespace std; void zl(double num) int le**e=0; double a[8]; le**e = int)(num*10)%10; a[1] =le**e/5; a[0] =le**e%5)/1; a[7] =num/50; a[6] =int)num%50)/20; a[5] =int)num%50)%20)/10; a[4] =int)num%50)%20)%10)/5; a[3] =int)num%50)%20)%10)%5)/2; a[2int)num%50)%20)%10)%5)%2)/1; if(a[0]!=0) cout<<"需要找的0.1元个数为：" cout<<"需要找的0.5元个数为：" cout<<"需要找的1元个数为：" cout<<"需要找的2元个数为：" cout<<"需要找的5元个数为：" cout<<"需要找的10元个数为：" cout<<"需要找的20元个数为：" cout<<"需要找的50元个数为："< int main() double num; cout<<"请输入你需要找的零钱数：" zl(num); cout< return 0; 2）实验结果比较。 上一步骤中两个源**运行结果分别如下： 第一个的运行结果。 第二个运行结果。 比较上面两个算法，第二个算法在第一个的基础上增加了输入输出功能，方便得到任意数值零钱问题的最优解。 五、结论与展望。 1） 算法实现的复杂度在问题规模很大时可以接受吗？ 一 课程题目。零钱问题贪心算法实现。二 课程摘要。1 题目描述。使用贪心算法设计思想设计算法实现找零钱问题。例题13 4一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为25美分 10美分 5美分 及1美分的硬币。售货员分步骤组成... 课程名称 算法分析与设计课程设计 设计题目 砸手机游戏 课程设计 大作业 报告。一 课题背景。中国民族原创网络游戏为中国网络游戏产业所做出了巨大贡献，民族原创网络游戏已经成为产业发展的主导力量。同样在中国自主研发的民族原创网络游戏已经真正成为中国游戏市场的主导力量。网络游戏是通过信息网络传播和实现的... 计通学院。课程设计报告。课程名称 算法设计与分析 题目名称。学生学院 计通学院 专业班级。学号。学生姓名。指导教师。年月日。目录。正文具体内容参考 包括问题的提出背景 研究历史等内容。陈述解决该问题所需要的方法，以及方法的基本思路和步骤等。陈述解决问题的思路，关键问题的解决方法。具体的算法描述，伪 ...算法设计与分析课程设计
算法分析与设计课程设计
《算法设计与分析》课程设计