贪心算法----活动时间安排

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

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

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

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

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

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

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

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

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

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

例：给出待安排的11个活动的开始时间和结束时间，要求安排尽量多项活动使用会场。

首先，任意输入这11个活动。

然后对活动以其完成时间的非减序排列。

（意义：使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。

）将第一次活动结束时间f[1]与后面活动开始时间s[2]相比较，若s[2]<f[1]则继续比较，直到s[4]>f[1]，选中此活动。

再用活动4的结束时间f[4]与其后活动的开始时间比较……同理类推，直到比较完成为止，最后选出合条件的活动1，活动4，活动8和活动11，它们将依次被安排使用该场地。

【调试分析和心得体会】运行依算法写出的程序并分析算法实现的时间复杂度情况。

1.程序源码：#include <iostream>using namespace std;class B{int dataT[11],dataF[11]; //使用两个数组一个放开始时间，一个放结束时间public :void cinP();//用户输入，获得数据void paiXu();//排序void dispaly();//输出排序后的数据void last();//使用贪心算法后得得到的结果};void B::cinP(){for(int i=0;i<11;i++){cout<<"请输入开始时间："<<endl;cin>>dataT[i];cout<<"请输入结束时间："<<endl;cin>>dataF[i];}}void B::paiXu(){int munT=0;//实现数据交换的一个中间量int numF=0;//实现数据交换的一个中间量for(int r=0;r<11;r++){for(int j=r+1;j<11;j++){if(dataF[r]>dataF[j]){//对结束时间排序，同时同步改变与之对应的开始时间//保持开始时间和结束时间配套numF=dataF[j];dataF[j]=dataF[r];dataF[r]=numF;//交换结束时间munT=dataT[j];dataT[j]=dataT[r];dataT[r]=munT;//交换开始时间}}}}void B::dispaly(){for(int y=0;y<11;y++){cout<<dataT[y]<<"\t";}cout<<endl;for(int y1=0;y1<11;y1++){cout<<dataF[y1]<<"\t";}void B::last(){int dataQ[11],dataH[11];int g=0;dataQ[0]=dataT[0];dataH[0]=dataF[0];//将一个节目结束时间和另一个节目开始时间进行对比//将符合条件的节目的开始时间和结束时间分别保存在数组，dataQ和dataH中for(int w=1;w<11;w++){if(dataH[g]<=dataT[w]){g++;dataQ[g]=dataT[w];dataH[g]=dataF[w];}}cout<<endl<<endl;for(int ye=0;ye<=g;ye++){cout<<dataQ[ye]<<"\t";}cout<<endl;for(int y1e=0;y1e<=g;y1e++){cout<<dataH[y1e]<<"\t";}}int main(int argc, char** argv) {B b;b.cinP();b.paiXu();b.dispaly();st();return 0;}2.运行结果：3.时间复杂度分析：本程序运用的核心数据结构是数组，由于存在两层for循环因此分析得出时间复杂度为：。

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

⾸先把⼀个活动的开始时间和结束时间放在两个数组中再进⾏排序，这样得到的就是最⼩开始时间和最⼩结束时间，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;
}。

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

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

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

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

）【数据输⼊】由⽂件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坐标之后写⼊。

贪心算法经典例题贪心算法是一种求解最优问题的算法思想，其核心理念是每一步都选择当前最优的策略，从而达到全局最优解。

贪心算法可以应用于许多经典问题，下面将介绍几个常见的贪心算法经典例题及相关参考内容。

1. 会议室安排问题题目描述：给定一组会议的开始时间和结束时间，求解如何安排会议，使得尽可能多的会议可以在同一时间段内进行。

解题思路：贪心算法可以通过每次选择结束时间最早的会议来求解。

首先将会议按照结束时间排序，选择第一个会议作为首先安排的会议，然后依次选择后续结束时间不冲突的会议进行安排。

相关参考内容：- 《算法导论》第16章：贪心算法（ISBN: 9787115265955）- 《数据结构与算法分析》第13章：贪心算法（ISBN: 9787302483626）2. 零钱兑换问题题目描述：给定一定面额的硬币，求解如何用最少的硬币数量兑换指定金额的零钱。

解题思路：贪心算法可以通过每次选择面额最大且不超过目标金额的硬币来求解。

从面额最大的硬币开始，尽可能多地选择当前面额的硬币，并减去已经选择的硬币金额，直到金额为0。

相关参考内容：- 《算法导论》第16章：贪心算法（ISBN: 9787115265955）- 《算法4》第1章：基础（ISBN: 9787302444627）3. 区间调度问题题目描述：给定一组区间，求解如何选择尽可能多的不重叠区间。

解题思路：贪心算法可以通过每次选择结束时间最早的区间来求解。

首先将区间按照结束时间排序，选择第一个区间作为首先选择的区间，然后依次选择后续结束时间不与已经选择的区间重叠的区间进行选择。

相关参考内容：- 《算法导论》第16章：贪心算法（ISBN: 9787115265955）- 《数据结构与算法分析》第13章：贪心算法（ISBN: 9787302483626）4. 分糖果问题题目描述：给定一组孩子和一组糖果，求解如何分配糖果，使得最多的孩子能够得到满足。

解题思路：贪心算法可以通过每次选择糖果最小且能满足当前孩子的糖果来求解。

列举用贪心算法求解的经典问题
1. 零钱兑换问题：给定一些面值不同的硬币和一个金额，要求用最少的硬币凑出这个金额。

2. 最小生成树问题：给定一个无向带权图，要求用最小的权值构建一棵生成树。

3. 背包问题：给定一些物品和一个背包，每个物品有对应的价值和重量，要求在背包容量限制下，选取物品使得总价值最大。

4. 活动安排问题：有若干个活动需要分配一段时间，每个活动有对应的开始时间和结束时间，要求选取尽可能多的活动，使得任两个安排的活动时间不重叠。

5. 单源最短路径问题：给定一个有向带权图和一个起始节点，要求求出从起始节点到其他所有节点的最短路径。

6. 任务调度问题：有若干个需要完成的任务和多个可执行任务的处理器，要求将任务分配给处理器，使得执行总时间最小。

7. 区间覆盖问题：给定一些区间，要求用尽可能少的区间覆盖整个线段。

8. 哈夫曼编码问题：给定一些字符及其对应的出现概率，要求用最短的编码方式表示这些字符。

西安邮电大学（计算机学院）课内实验报告实验名称：贪心算法专业名称：计算机科学与技术班级：学生姓名：学号（8位）：指导教师：实验日期： 2014年5月22日1．实验目的及实验环境实验目的：通过实际应用熟悉贪心算法，并解决会场安排问题、多出最优服务次序问题实验环境：Visual C++ 6.0二. 实验内容1.会场安排问题.假设要在足够多的回厂里安排一批活动，并希望使用尽可能少的会场，设计一个有效的贪心算大进行安排（这个问题实际上是注明的图着色问题。

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

使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数）2.多处最优服务次序问题设有n个顾客同时等待一项服务。

顾客i需要的服务时间为ti，1<=i<=n。

共有s处可以提供此项服务。

应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。

三．方案设计1、设有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相容。

由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。

直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。

也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。

算法greedySelector的效率极高。

当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。