采用C++实现区间图着色问题(贪心算法)实例详解
本文所述算法即假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有活动。采用C++的贪心算法,来确定哪一个活动使用哪一间教室。
对于这个问题也常被称为区间图着色问题,即相容的活动着同色,不相容的着不同颜色,使得所用颜色数最少。
具体实现代码如下:
//贪心算法 #include"stdafx.h" #include<iostream> #defineN100 usingnamespacestd; structActivity { intnumber;//活动编号 intbegin;//活动开始时间 intend;//活动结束时间 boolflag;//此活动是否被选择 introomNum;//此活动在哪间教室举行 }; //对于活动集,按照结束时间递增排序,使用快速排序 voidfast_sort(Activity*act,intf,intt) { if(f<t) { inti=f-1,j=f; Activitya=act[t]; while(j<t) { if(act[j].end<=a.end) { i++; Activitytemp1=act[i]; act[i]=act[j]; act[j]=temp1; } j++; } Activitytemp2=act[t]; act[t]=act[i+1]; act[i+1]=temp2; fast_sort(act,f,i); fast_sort(act,i+2,t); } } //把每一个相容的活动集添加到一个教室,使得教室数目最少 intselect_room(Activity*act,int*time,intn) { inti=1; intj=1; intsumRoom; //目前所用的教室数目 sumRoom=1; intsumAct; //目前有多少活动被选择了 sumAct=1; //教室1目前最晚时间为排在最前面的活动的结束时间 time[1]=act[0].end; //最先结束的活动放在教室1中 act[0].roomNum=1; for(i=1;i<n;i++) { for(j=1;j<=sumRoom;j++) { //如果活动act[i]的开始时间大于等于j教室目前的最晚结束时间且此活动还没有被选择, //则此活动与目前这间教室里面的活动是兼容的,可以加入进去 if((act[i].begin>=time[j])&&(!act[i].flag)) { //此活动的教室号码 act[i].roomNum=j; //此活动被选择 act[i].flag=true; //更新此教室的最晚时间 time[j]=act[i].end; //被选择的活动数目加1 sumAct++; } } //说明活动没有全部被选择,而所有活动都遍历一遍 //所以需要再加一个教室,从头再遍历 if(sumAct<n&&i==n-1) { //从头开始遍历 i=0; //教室数目加1 sumRoom=sumRoom+1; } } returnsumRoom; } int_tmain(intargc,_TCHAR*argv[]) { intcases; Activityact[N]; //用来记录每个教室目前最晚完成的活动的结束时间 inttime[N]; cout<<"请输入案例的个数:"<<endl; cin>>cases; while(cases--) { intn; cout<<"请输入活动的数目:"<<endl; cin>>n; inti; for(i=0;i<n;i++) { time[i+1]=0;//初始化每个教室目前最晚的时间为0 act[i].number=i+1; act[i].flag=false;//初始化每个活动都未被选择 act[i].roomNum=0;//初始化每个活动都占用教室 cout<<"活动"<<i+1<<"开始时间:"; cin>>act[i].begin; cout<<"活动"<<i+1<<"结束时间:"; cin>>act[i].end; } fast_sort(act,0,n-1); introomNum=select_room(act,time,n); cout<<"所用教室总数为:"<<roomNum<<endl; cout<<"每个活动在哪一个教室中:"<<endl; for(i=0;i<n;i++) { cout<<"活动"<<act[i].number<<"在教室"<<act[i].roomNum<<"中"<<endl; } } system("pause"); return0; }