实验二 贪心算法-最少活动会场安排问题

实验报告
课程名称：算法设计与分析实验名称：贪心法解活动安排问题任课教师：专业：计算机科学与技术
班级: 20xx 级x班学号：
姓名：完成日期： 20xx年x月xx日
五、实验总结
在做本实验之前，自己看了课本上所列举的贪心法解活动安排问题的代码，代码很简单，很容易理解，于是就按课本的代码实现。

通过几个测试用例测试发现结果不对，后来发现自己忘了进行贪心法的一个前提条件，事先没有按各个活动结束时间对所有活动进行非递减排序，所以才会导致结果错误。

经过修正后，自己真正理解了贪心法解活动安排问题的原理，重新完成本次实验内容也是很顺利，在编程方面没有遇到什么困难。

实验报告
课程名称：算法设计与分析实验名称：贪心法解活动安排问题任课教师：专业：计算机科学与技术
班级: 20xx 级x班学号：
姓名：完成日期： 20xx年x月xx日
五、实验总结
在做本实验之前，自己看了课本上所列举的贪心法解活动安排问题的代码，代码很简单，很容易理解，于是就按课本的代码实现。

通过几个测试用例测试发现结果不对，后来发现自己忘了进行贪心法的一个前提条件，事先没有按各个活动结束时间对所有活动进行非递减排序，所以才会导致结果错误。

经过修正后，自己真正理解了贪心法解活动安排问题的原理，重新完成本次实验内容也是很顺利，在编程方面没有遇到什么困难。

活动安排public static int greedySelector(int [] s, int [] f, boolean a[]){ //s[]开始时间f[]结束时间int n=s.length-1;a[1]=true;int j=1;int count=1;for (int i=2;i<=n;i++){ if (s[i]>=f[j]) { a[i]=true; j=i; count++; }else a[i]=false;}return count;}背包问题void Knapsack(int n,float M,float v[],float w[],float x[]){ Sort(n,v,w); //以每种物品单位重量的价值Vi/Wi从大到小排序int i;for (i=1;i<=n;i++) x[i]=0;float c=M;for (i=1;i<=n;i++){ if (w[i]>c) break;x[i]=1;c-=w[i];}if (i<=n) x[i]=c/w[i]; //允许放入一个物品的一部分}最优装载void Loading(int x[], T ype w[], T ype c, int n){ int *t = new int [n+1]; //t[i]要存的是w[j]中重量从小到大的数组下标Sort(w, t, n); //按货箱重量排序for (int i = 1; i <= n; i++) x[i] = 0; //O(n)for (int i = 1; i <= n && w[t[i]] <= c; i++){x[t[i]] = 1; c -= w[t[i]];} //调整剩余空间}单源最短路径Dijiksratemplate<class Type>void Dijikstra(int n, int v, Type dist[], int prev[], Type **c){ //c[i][j]表示边(i,j)的权，dist[i]表示当前从源到顶点i的最短特殊路径bool s[maxint];for(int i= 1;i<=n; i++){ dist[i]=c[v][i]; s[i]=false;if(dist[i]==maxint) prev[i]=0;else prev[i]=v;}dist[v]=0 ; s[v]=true;for(int i=1;i<n;i++){ int temp = maxint, u = v;for(int j= 1;j<=n; j++)if( (!s[j])&&(dist[j]<temp) )｛u= j ; temp=dist[j]; ｝s[u]= true;for(int j= 1;j<=n;j++)if( (!s[j])&&(c[u][j])<maxint){ Type newdist = dist[u]+c[u][j];if(newdist<dist[j]) {dist[j]= newdist; prev[j]=u; } }}//ENDFOR}//END找零钱问题#define NUM 4void main(){ int m[NUM]={25,10,5,1};int n; //假设n=99cin>>n;cout<<n<<"的找钱方案为：";for(int i=0;i<NUM;i++)while(n>=m[i]&&n>0){cout<<m[i]<<" ";n-=m[i];}}//END多机调度#define N 10#define M 3void sort(int t[],int n);int set_work1(int t[],int n);int max(int t[],int num);int min(int t[],int m);int set_work2(int t[],int n);static int time[N]={2,8,18,32,50,72,98,128,182,200},s[M]={0,0,0};void main(){sort(time,N);if(M>=N) //作业数小于机器数cout<<set_work1(time,N)<<endl;elsecout<<set_work2(time,N)<<endl;}void sort(int t[],int n){for(int k=0;k<n-1;k++) //用选择法将处理时间从大到小排序{int j=k;for (int i=k; i<n; i++)if (t[i]>t[j]) j=i;{int temp=t[j];t[j]=t[k];t[k]=temp;}}}int max(int t[],int num) //max函数求解处理时间总和最长{int max=t[0];for(int i=1;i<num;i++)if(max<t[i]) max=t[i];return max;}int min(int t[],int m){int min=0; //min记录目前处理作业时间和最小的机器号for(int i=1;i<m;i++)if(s[min]>s[i]) min=i;return min;}int set_work1(int t[],int n){ int m=0;for(int i=0;i<n;i++) //分派作业s[m++]+=t[i];return max(s,N);}int set_work2(int t[],int n){ for(int i=0;i<n;i++)s[min(s,M)]+=t[i];return max(s,M);}。

贪⼼算法（会场安排问题、区间选点）学习算法课程之后的第⼀次记录，渐渐的，程序设计考虑的因素增多，程序=数据结构+算法，这个等式让我深有体会。

从开始简单的C++编程，再到选择合适数据结构，现在需要更进⼀步，从算法层次上考虑程序执⾏的效率。

我对算法的理解是⽤更少的开销获得更优的执⾏效果。

分治法、动态规划在此之前没有记录下来，学到贪⼼算法的时候，觉得需要总结⼀下学过的东西，也能更好的理解。

动态规划的设计，要满⾜最优⼦结构性质和重叠⼦问题，采⽤⾃底向上的策略，计算出最优值，找到整体最优解。

这个过程有时候挺难的，主要在写出递归式，要⾃底向上填表。

贪⼼策略有点像动态规划，但在⼀些⽅⾯是不同的，有时候贪⼼算法的思想更容易想到。

它要满⾜⼦问题最优⽽得到整体最优？两个条件：最优⼦结构性质和贪⼼选择性质。

满⾜贪⼼选择性质⼀定满⾜最优⼦结构性质，⽽满⾜最优⼦结构性质不⼀定满⾜贪⼼选择性质，⽐如背包问题可以⽤贪⼼算法解决，⽽0-1背包问题只能⽤动态规划。

典型的贪⼼问题活动安排，有n个活动，给出开始时间和结束时间，要尽可能安排多的活动（时间互相不冲突）。

解决这个问题正确的贪⼼思想是以每个活动结束时间为⽐较变量，按结束时间升序排好活动次序，接着就进⾏⽐较选择。

⽽会场安排问题与活动⼜有些不同之处，下⾯是我的解题过程。

7-2 会场安排问题 (20 分)假设要在⾜够多的会场⾥安排⼀批活动，并希望使⽤尽可能少的会场。

设计⼀个有效的贪⼼算法进⾏安排。

（这个问题实际上是著名的图着⾊问题。

若将每⼀个活动作为图的⼀个顶点，不相容活动间⽤边相连。

使相邻顶点着有不同颜⾊的最⼩着⾊数，相应于要找的最⼩会场数。

）输⼊格式:第⼀⾏有 1 个正整数k，表⽰有 k个待安排的活动。

接下来的 k⾏中，每⾏有 2个正整数，分别表⽰ k个待安排的活动开始时间和结束时间。

时间以 0 点开始的分钟计。

输出格式:输出最少会场数。

输⼊样例:51 2312 2825 3527 8036 50输出样例:3#include<iostream>#include<algorithm>using namespace std;struct node {int begin;int end;int flag;//标记该活动是否被安排，0表⽰未安排，1表⽰已安排}t[10001];int cmp(const node &a,const node &b)//⽐较规则：以结束时间升序排列{return a.end<b.end;}int main(){int i,j,n;node temp;cin>>n;for(i=0;i<n;i++){cin>>t[i].begin>>t[i].end;t[i].flag=0;}sort(t,t+n,cmp);int sum=0;//总共需要的会场数量for(i=0;i<n;i++)//⽅法2{if(!t[i].flag)//找到未安排的活动，进⾏场地安排{sum++;int p=i;for(j=p+1;j<n;j++)//当前活动结束时间与下⼀个活动开始不相交，则安排到同⼀个会场{if(t[p].end<=t[j].begin&&!t[j].flag){p=j;t[j].flag=1;}}t[i].flag=1;}}cout<<sum;return0;}View Code贪⼼策略为：把尽可能多的时间互不冲突的活动安排到⼀个会场，若活动时间交叉，则在安排到另⼀个会场。

会场安排问题（贪⼼）
思路：
能放在⼀个会场⾥的活动的前提是，当前活动的开始时间⼤于等于上⼀个活动的结束时间。

⾸先把⼀个活动的开始时间和结束时间放在两个数组中再进⾏排序，这样得到的就是最⼩开始时间和最⼩结束时间，k初值为0，只要当前的开始时间⼩于结束时间，k++，由于结束时间是降序的，如果不⼩于这个结束时间，就后移⼀位，这样就得到了会场的次数。

贪⼼算法的思想就是只考虑当前的情况。

⽽不顾虑全局最优，所以我们只要能保证下⼀个活动的开始时间能⼩于这个活动的结束时间就⾏。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int a[10005],b[10005];
for(int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
}
sort(a,a+n);
sort(b,b+n);
int k = 0,j = 0;
for(int i = 0; i < n; i++) {
if(a[i] < b[j]) k++;
else j++;
}
cout << k << endl;
return0;
}。

活动安排问题，对每项活动的按照结束时间非减序排列。

然后选第一个。

按照第一个的结束时间来看接下去怎么选，以此类推。

•第一步二-选择活动1作为第一个被选中的活动，并将活动1的结束时间作为判断下一个活动是否被选中的依据；•第二步’-判断活动2与活龙T是否相容-即引2］是否大于或等于耳］；1结果土不相容，活动2没有被选中，活动1的结束时间仍作为判断下一个活动是否被选中的依据•第三步M-判断活动3与活或T是否相容•即引3］是否大于或等于耳1］：结果士不相容，活动礙有被选中，活动1的结束时间仍作为判断下一个活动是否被选中的依据•第四步&-判斷活动4与活动T是否相容-即H4］是否大于或等于di］：结果：相容，活动4袱选中，活动4的结束时间将作为判断下一个活动是否被选中的依据10贪心选择性质的证明：1.活动安排问题的一个最优解是以贪心选择开始。

即最优解包含第一个活动（叫做活动1 ）。

证明：假设有一个最优解叫做A。

它的活动也是以结束时间的非减序进行排列。

假设A中第一个活动叫做K。

如果K是我们的活动1，则A就是以活动1开始的。

如果K不是活动1•则把K从A中去掉，并加上活动1,而且活动1是相容的是因为活动1的结束时间最早。

所以证明了活动安排问题的一个最优解是以贪心选择开始。

最优子结构的证明：把起始时间大于活动1的结束时间的活动去掉，A也可以把K去掉，这样子有一个递推的关系就是（总活动中）接下去那个与活动1相容的解必然可以相容在最优解（A-K）里面。

（因它又可以化为一个贪心选择的开始）所以每一步做出的贪心选择将使得原问题化为规模变小的相似的子问题。

实验二：贪心算法
【实验目的】
应用贪心算法求解活动安排问题。

【实验性质】
验证性实验。

【实验要求】
活动安排问题是可以用贪心算法有效求解的很好的例子。

问题：有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。

求解：安排尽量多项活动在该场地进行，即求A的最大相容子集。

设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下：
将此表数据作为实现该算法的测试数据。

【算法思想及采用的数据结构】
【程序代码】
【运行结果】
【算法分析和心得体会】
附加题：
【实验要求】
需要在某个城市的n个居民区之间铺设煤气管道，则在这n个居民区之间只要铺设n-1条管道即可。

假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同。

选择最优的施工方案能使总投资尽可能少，这个问题即为求网的“最小生成树”问题。

参照以下居民区示意图，使得求解算法为：在可能架设的m条管道中选取n-1条，既能连通n-1个居民区，有使总投资达到“最小”。

网可采用邻接矩阵为存储结构，以定点对（i,j）
应用贪心算法策略，采用普里姆算法或Kruskal算法来求解居民区示意图的最小生成树，采用合适的数据结构。

用C语言或C++语言编写程序代码，选上述居民区示意图中的数据作为测试数据。

并调试输出正确结果。

【算法思想及采用的数据结构】
【程序代码】
【运行结果】
【算法分析和心得体会】。

贪心算法解决活动安排问题研究摘要：利用贪心算法解决如何使用最少的资源安排一系列活动。

并证明了贪心算法解决此问题的有效性，且进行了实例验证，并进行了复杂度分析，此算法是解决资源组合规划问题较好的方法。

关键词：贪心算法；java程序；复杂度分析；活动安排问题中图分类号：tp312文献标识码：a文章编号：16727800（2011）012004302基金项目：广西研究生教育创新计划（22m58）作者简介：苏方方（1986-），女，河南商丘人，广西师范大学计算机科学与信息工程学院硕士研究生，研究方向为自然语言处理和算法；张金玲（1986-），女，山东菏泽人，广西师范大学计算机科学与信息工程学院硕士研究生，研究方向为远程教育和算法。

0引言假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。

这里就需要选用合适的算法来解决类似的问题。

虽然计算机的计算能力每年都在飞快增加，但是，需要处理的信息量更是呈指数级的增长。

互联网的信息流量在飞快进步，数据量更是达到了前所未有的程度。

无论是三维图形，海量数据处理等都需要极大的计算量。

在网络时代，越来越多的挑战需要靠卓越的算法来解决。

1贪心算法以及贪心算法的基本要素贪心算法是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。

并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解。

贪心算法可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理。

也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。

贪心算法解题步骤：①从问题的某个初始解出发；②采用循环语句，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模；③将所有部分解综合起来，得到问题的最终解。

另外它也是一种某种度量意义下的最优解的分级处理方法。

对于一个具体的问题，怎么知道是否可用贪心算法来解决问题，以及能否得到问题的一个最优解呢？从许多可以用贪心算法求解的问题中可以看到它们一般具有两个重要的性质：①贪心选择性质；②最优子结构性质。

贪⼼算法之会场安排问题【问题描述】假设要在⾜够多的会场⾥安排⼀批活动，并希望使⽤尽可能少的会场。

（这个问题实际上是著名的图着⾊问题。

若将每⼀个活动作为图的⼀个顶点，不相容活动间⽤边相连。

使相邻顶点有不同颜⾊的最⼩着⾊数，相应于要找的最⼩会场数。

）【数据输⼊】由⽂件input.txt给出输⼊数据，第⼀⾏⼜⼀个正整数K，表⽰有K个待安排的活动。

接下来有K⾏数据，每⾏有两个正整数，分别表⽰K个待安排的活动的开始时间和结束时间。

【结束输出】输出最少会场数。

input.txt output.txt5 31 2312 2825 3527 8036 50来吧，帮你解决介个问题。

思路：按照俺的思路啊~遍历所有的活动时间，设⼀个int sum代表会场的个数，如果时间可叠加到前⾯已有活动的会场的，把活动加到已有会场的数组中；如不可叠加，则新加会场重新加⼀个数组把这个新会场加⼊到新数组中然后sum+1。

遍历到最后 sum则就是需要最少的会场的个数·····下次再来。

我回来了，上⾯的思路我尝试了，没试出来。

就换了⼀种思路，就是做标记，已经加⼊的会场标记为1 否则为0 就OK了代码下次贴上#include <stdio.h>#define LEN 6int sum=0;int mark[LEN];void squarePlan(int s[],int f[]){int k=1,j;int flag=1;mark[0]=mark[1]=1;while(flag==1){mark[k]=1;for(int m=k+1;m<=LEN;m++){if(mark[m]==0&&s[m]>=f[k]){mark[m]=1;k=m;}}sum++;for(j=2;j<LEN;j++){if(mark[j]==0){k=j;break;}}flag=0;for(int i=1;i<LEN;i++){if(mark[i]==0&&i!=j){flag=1;break;}}}}int main(){ int s[LEN],f[LEN];int n;FILE *fp_in,*fp_out;fp_in=fopen("input.txt","r");//打开⼀个输⼊流，读取input.txt⽂件fp_out=fopen("output.txt","w");//打开⼀个输出流，写output.txt⽂件if(fp_in==NULL){printf("open in file failed\n");return 0;}if(fp_out==NULL){printf("open out file failed\n");return 0;}fscanf(fp_in,"%d",&n);s[0]=0;f[0]=0;for(int i=1;i<=n;i++){fscanf(fp_in,"%d",&s[i]);//x坐标在此题中⽆⽤，⽽y坐标在x坐标之后写⼊。

贪心算法解决活动安排问题金潇Use the greedy algorithm to solve the arrangement for activitiesJinxiao摘要：贪心算法在当前来看是最好的选择。

是用利用启发式策略，在不从整体最优上加以考虑的情况下，来做出局部最优选择的一种算法。

本文通过贪心算法的经典案例—活动安排问题入手，描述了贪心算法的基本思想和可能产生的问题，并简述该算法的好处和特点，最后给出几种经典的贪心算法。

关键字：贪心算法、局部最优选择Abstract:A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum. This article through the greedy algorithm of the classic case--activities problems, describes the greedy algorithm the basic ideas and possible problems, and briefly introduces the advantages and characteristics of the algorithm, and finally gives several classic the greedy algorithm. Keywords：greedy algorithm、the locally optimal choice1.引言：贪心法是一种改进了的分级处理方法。

用贪心法设计算法的特点是一步一步地进行，每一步上都要保证能获得局部最优解。

贪心算法实验报告课程数据结构与算法实验名称贪心策略第页班级学号姓名实验日期：2019年9月15日报告退发(订正、重做)一、实验目的掌握贪心策略的原理和应用。

二、实验环境1、微型计算机一台2、WINDOWS操作系统，Java SDK，Eclipse开发环境三、实验内容必做题：1、编写程序，求解普通背包问题，要求输出背包所能容纳物品的最大价值(最优值)，及与该最大价值相应的装入背包中的每件物品信息。

2、设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。

每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。

如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。

若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。

也就是说，当si≥fj或sj≥fi时，活动i与活动j 相容。

编写程序，在所给的活动集合中选出最大的相容活动子集合。

要求输出活动数量(即最优值)和最大相容活动子集中的每个活动(即最优解)。

四、实验步骤和结果(附上代码和程序运行结果截图)1、普通背包问题//goods.classpublic class goods implements Comparable<goods> {private static int ids=1;private int id;private int weight;private int value;private int use;//初始化对象//public goods(int w,int v){super();id=ids++;weight=w;value=v;use=0;}//获取输出值//public float getVW(){return this.value/this.weight;}public int getw(){return this.weight;}public int getv(){return this.value;}public int getuse(){return e;}//输出设置//public void setuse(int u){e=u;}//方法//public int compareTo(goods o){if(this.value*o.weight>o.value*this.weight) return -1;//使用交叉相乘的方法避免除法，a/b?c/d=ad?bcif(this.value*o.weight<o.value*this.weight) return 1;return 0;}public String toString(){return"物品编号"+this.id+" 物品重量"+this.weight+" 物品价值"+this.value+" 物品使用情况"+e;}}//NormalBagimport java.util.ArrayList;import java.util.PriorityQueue;public class NormalBag {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stub//初始化队列//PriorityQueue<goods> pq=initpq();//定义暂存结果数组//ArrayList<goods> place=new ArrayList<goods>();//初始化背包值//int c=10;//背包当前容量int v=0;//背包当前价值//开始放入物品//goods t;//设定暂存记录变脸while(true){//设定借宿条件//if(c==0)break;if(pq.isEmpty())break;//取出替换元素//t=pq.poll();//开始比较//if(t.getw()<=c){v+=t.getv();t.setuse(t.getw());c-=t.getw();}else{v+=c*t.getVW();t.setuse(c);c=0;}place.add(t);}//输出结果//System.out.println(v);System.out.println(place);}//创建队列元素private static PriorityQueue<goods> initpq() {// TODO Auto-generated method stubPriorityQueue<goods>pq=new PriorityQueue<goods>();pq.offer(new goods(2,6));pq.offer(new goods(2,3));pq.offer(new goods(6,5));pq.offer(new goods(5,4));pq.offer(new goods(4,6));return pq;}}2.活动安排问题public class GreedySelector {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stub//初始化//int s[]={1,3,0,5,3,5,6,8,8,2,12};//开始时间数组，已排序int f[]={4,5,6,7,8,9,10,11,12,13,14};//结束时间数组，已排序int a[]=new int[s.length];//定义标记选择过的活动数组int count=0;//活动数量计数器//开始选择//greedyselector(s,f,a);//输出//for(int i=0;i<s.length;i++){//输出活动序号if(a[i]==1){System.out.print("活动"+(i+1)+" ");count++;}}System.out.println();System.out.print("活动总数量为："+count);//输出总活动数量}private static void greedyselector(int[] s, int[] f, int[] a) { // TODO Auto-generated method stub//贪心选择为，先结束的互动优先，这样剩余的时间达到最大，安排活动最多//int n=s.length-1;a[0]=1;//最先的那个最优int j=0;for(int i=1;i<=n;i++){if(s[i]>=f[j]){a[i]=1;j=i;}elsea[i]=0;}}}五、实验总结(本次实验完成的情况，心得体会)。

中原工学院计算机学院实验报告实验项目名称实验二、最少活动会场安排问题课程名称算法设计与分析学生姓名梁斐燕学生学号************所在班级网络14卓越学科专业网络工程任课教师吴志刚完成日期2016年月日实验二最少活动会场安排问题一、实验目的1．掌握贪心算法的基本概念和两个基本要素2．熟练掌握贪心算法解决问题的基本步骤。

3．学会利用贪心算法解决实际问题。

二、实验内容•问题描述：•题目一：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。

设计一个有效的贪心算法来进行安排，试编程实现。

•题目二：一辆汽车加满油后,可行使n千米。

旅途中有若干个加油站。

若要使沿途加油次数最少,设计一个有效算法，指出应在哪些加油站停靠加油。

•数据输入：个人设定，由键盘输入。

•要求：–上述题目任选一做。

上机前，完成程序代码的编写–独立完成实验及实验报告三、实验步骤㈠、数据结构与核心算法的设计描述提示：题目一：参考教材活动安排问题；有关队列操作参考数据结构。

void GreedySelector(int n, int *s, int *f, int *A) {//用集合A来存储所选择的活动A[1] = TURE; //默认从第一次活动开始执行int j = 1; //j记录最近一次加入到A中的活动for (int i = 2; i <= n; i++) { //f[j]为当前集合A中所有活动的最大结束时间//活动i的开始时间不早于最近加入到集合A中的j的时间f[j]if (s[i] >= f[j]) {A[i] = TURE; //当A[i]=TURE时，活动i在集合A中j = i;}else A[i] = FALSE;}}㈡、函数调用及主函数设计㈢程序调试及运行结果分析㈣实验总结在做本实验之前，自己看了课本上所列举的贪心法解活动安排问题的代码，代码很简单，很容易理解，于是就按课本的代码实现。

通过几个测试用例测试发现结果不对，后来发现自己忘了进行贪心法的一个前提条件，事先没有按各个活动结束时间对所有活动进行非递减排序，所以才会导致结果错误。

贪心算法实验报告贪心算法实验报告引言：贪心算法是一种常用的算法设计思想，它在求解最优化问题中具有重要的应用价值。

本实验报告旨在介绍贪心算法的基本原理、应用场景以及实验结果，并通过实例加以说明。

一、贪心算法的基本原理贪心算法是一种以局部最优解为基础，逐步构建全局最优解的算法。

其基本原理是在每一步选择中都采取当前状态下最优的选择，而不考虑之后的结果。

贪心算法通常具备以下特点：1. 贪心选择性质：当前状态下的最优选择一定是全局最优解的一部分。

2. 最优子结构性质：问题的最优解可以通过子问题的最优解来构造。

3. 无后效性：当前的选择不会影响以后的选择。

二、贪心算法的应用场景贪心算法适用于一些具有最优子结构性质的问题，例如：1. 路径选择问题：如Dijkstra算法中的最短路径问题，每次选择当前距离最短的节点进行扩展。

2. 区间调度问题：如活动选择问题，每次选择结束时间最早的活动进行安排。

3. 零钱找零问题：给定一些面额不同的硬币，如何用最少的硬币凑出指定的金额。

三、实验设计与实现本次实验选择了一个经典的贪心算法问题——零钱找零问题，旨在验证贪心算法的有效性。

具体实现步骤如下：1. 输入硬币面额和需要凑出的金额。

2. 对硬币面额进行排序，从大到小。

3. 从面额最大的硬币开始，尽可能多地选择该面额的硬币，直到不能再选择为止。

4. 重复步骤3，直到凑出的金额等于需要凑出的金额。

四、实验结果与分析我们通过对不同金额的零钱找零问题进行实验，得到了如下结果：1. 当需要凑出的金额为25元时，贪心算法的结果为1个25元硬币。

2. 当需要凑出的金额为42元时，贪心算法的结果为1个25元硬币、1个10元硬币、1个5元硬币、2个1元硬币。

3. 当需要凑出的金额为63元时，贪心算法的结果为2个25元硬币、1个10元硬币、1个1元硬币。

通过实验结果可以看出，贪心算法在零钱找零问题中取得了较好的效果。

然而，贪心算法并不是适用于所有问题的万能算法，它的有效性取决于问题的特性。