实验报告题目 实验四 贪心算法
开课实验室：数学实验室
指导老师：韩逢庆
时间：2011.12 学院：理学院
专业：信息与计算科学
班级：2009级2班 姓名：古 月
学号：09180230
一、实验目的
1．加深学生对贪心算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。
二、实验内容
题目见P143:4-16,4-23.
三、实验要求
（1）用分治法求解最少加油次数和最少硬币个数问题；
（2 ）再选择自己熟悉的其它方法求解本问题；
（3）上机实现所设计的所有算法；
四、实验过程设计（算法设计过程） （1） 最少加油次数 实验题目
一辆汽车加满油以后可以行使n公里，旅途中有若干个加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿路加油次数最少。并证明算法能产生一个最优解。 过程设计
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说最少加油次数的问题。在这个算法中，我采用的贪心算法的策略。首先人机互动的设定加满油以后最长能够行使的距离，然后输入了各个站点之间的距离，在程序的设计中，首先检查了程序的可行性。要是遇到当某两个站点之间的距离大于汽车一次加油以后所能够行使的最大距离时，我们认为此问题是不可行的。这个在实际情况中也是很容易理解的。然后在满足可行性条件下，依次采用贪心算法对问题得以实现。采用s这个来保存现在车里面留下的油，当此时留下的有能够行驶完这一站点到下一站点之间的距离是，在这一站点的时候就不加油。但是若不能行使完这一段路程的时候，就加满油。核心算法如下：
for(i=0,s=0;i
{
s=s+a[i];
if(s>n)
{
sum++;
s=a[i];
}
} （2） 最少硬币个数问题 实验题目
考虑下面的用最少硬币个数找出n分钱的问题：
当使用2角5分，1角，5分和1分四种硬币面值时，设计一个找n分钱的贪心算法，并证明算法能产生最优解。 过程设计
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说找最少硬币个数的问题。在算法的实现过程中，当剩余的钱数大于2角5分时，我们在记录找2角5分硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减2角5分。不断重复这个过程，直到剩余所需找的钱的数目小于2角5分时，在记录找1角硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减1角，不断重复这个过程，直到剩余所需找的钱的数目小于1角。5分和1分的硬币实现过程同上述过程一样，一直执行到所剩的钱的数目为0，此时停止计算，得到最优解。
五、实验结果分析 （1）最少加油次数
当加油后行驶的最大距离小于相邻站点的最小值时，此时，可行，求解结果如下：
当加油后行驶的最大距离大于相邻站点的最小值时，此时，没用可行性，为边沿情况，求解结果如下：
（分析时空复杂性，设计测试用例及测试结果） 时间复杂性：该算法的时间复杂度为O(n) 空间复杂性分析：该算法的空间复杂度为O(1) （2）最少硬币问题 当输入的找零钱数为正常的时候的运行情况如下：
当输入的找零钱数为不正常的时候（为负）的运行情况如下：
（分析时空复杂性，设计测试用例及测试结果） 时间复杂性：该算法的时间复杂性为O(n) 空间复杂性分析：该算法的空间复杂性为O(1)
六、实验体会
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题，相容活动安排问题等。这样和采用动态规划的算法相比，算法的思想更加的简单，实现起来更加的容易。
但是也要明确贪心算法和动态规划的主要区别。及0-1背包问题可以用动态规划算法求解，但是贪心选择算法却不能用动态规划算法求解。因为贪心算法无法最终将背包装满，部分闲置的背包空间使得每公斤背包空间的价值降低了。
七、附录：（源代码） （1） 最少加油次数 具体算法的实现如下：
#include void main() { int n,m,a[100],i,s,sum=0,j; cout>n; cin>>m; cout
cin>>a[i]; } for( i=0;i
cout
if(a[j]>m)
{
sum=-1;
break;
} if(sum!=-1) {
} for(i=0,s=0;i
s=s+a[i];
if(s>n)
{
sum++;
s=a[i];
} } } if(sum==-1) cout
#include main() { double n,m,a,b,c,d,f; a=b=c=d=0; cout>n; if(n
cout=2.5) {
a++;
m=m-2.5; } while(m>=1) {
b++;
m=m-1; } while(m>=0.5) {
c++;
m=m-0.5; } while(m>=0.1) {
d++;
m=m-0.1; } f=a+b+c+d; cout
