当前位置: 首页 > 编程笔记 >

采用C++实现区间图着色问题(贪心算法)实例详解

桂志新
2023-03-14
本文向大家介绍采用C++实现区间图着色问题(贪心算法)实例详解,包括了采用C++实现区间图着色问题(贪心算法)实例详解的使用技巧和注意事项,需要的朋友参考一下

本文所述算法即假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有活动。采用C++的贪心算法,来确定哪一个活动使用哪一间教室。

对于这个问题也常被称为区间图着色问题,即相容的活动着同色,不相容的着不同颜色,使得所用颜色数最少。

具体实现代码如下:

//贪心算法

#include "stdafx.h"
#include<iostream>
#define N 100
using namespace std;

struct Activity
{
 int number; //活动编号
 int begin; //活动开始时间
 int end; //活动结束时间
 bool flag;//此活动是否被选择
 int roomNum; //此活动在哪间教室举行
};
//对于活动集,按照结束时间递增排序,使用快速排序
void fast_sort(Activity *act,int f,int t)
{
 if(f<t)
 {
 int i = f-1,j = f;
 Activity a = act[t];
 while(j<t)
 {
  if(act[j].end<=a.end)
  {
  i++;
  Activity temp1 = act[i];
  act[i] = act[j];
  act[j] = temp1;
  }
  j++;
 }
 Activity temp2 = act[t];
 act[t] = act[i+1];
 act[i+1] = temp2;
 fast_sort(act,f,i);
 fast_sort(act,i+2,t);
 }
}
//把每一个相容的活动集添加到一个教室,使得教室数目最少
int select_room(Activity *act,int *time,int n)
{
 int i = 1;
 int j = 1;
 int sumRoom;
 //目前所用的教室数目
 sumRoom = 1; 
 int sumAct;
 //目前有多少活动被选择了
 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;
 }
 }
 return sumRoom;
}

int _tmain(int argc, _TCHAR* argv[])
{
 int cases;
 Activity act[N];
 //用来记录每个教室目前最晚完成的活动的结束时间
 int time[N];
 cout<<"请输入案例的个数:"<<endl;
 cin>>cases;
 while(cases--)
 {
 int n;
 cout<<"请输入活动的数目:"<<endl;
 cin>>n;
 int i;
 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);
 int roomNum =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");
 return 0;
}
 类似资料:
  • 本文向大家介绍C++贪心算法实现活动安排问题(实例代码),包括了C++贪心算法实现活动安排问题(实例代码)的使用技巧和注意事项,需要的朋友参考一下 贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后

  • 本文向大家介绍c语言来实现贪心算法之装箱问题,包括了c语言来实现贪心算法之装箱问题的使用技巧和注意事项,需要的朋友参考一下 装箱问题,贪心算法求近似最优解 以上就是本文的全部内容了,希望大家能够喜欢。

  • 本文向大家介绍python 贪心算法的实现,包括了python 贪心算法的实现的使用技巧和注意事项,需要的朋友参考一下 贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不

  • 本文向大家介绍Python贪心算法实例小结,包括了Python贪心算法实例小结的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python贪心算法。分享给大家供大家参考,具体如下: 1. 找零钱问题:假设只有 1 分、 2 分、五分、 1 角、二角、 五角、 1元的硬币。在超市结账 时,如果 需要找零钱, 收银员希望将最少的硬币数找给顾客。那么,给定 需要找的零钱数目,如何求得最少的硬币数

  • 本文向大家介绍C++ 搬水果贪心算法实现代码,包括了C++ 搬水果贪心算法实现代码的使用技巧和注意事项,需要的朋友参考一下 C++ 搬水果贪心算法实现代码 (1)题目描述:     在一个果园里,小明已经将所有的水果打了下来,并按水果的不同种类分成了若干堆,小明决定把所有的水果合成一堆。每一次合并,小明可以把两堆水果合并到一起,消耗的体力等于两堆水果的重量之和。当然经过 n‐1 次合并之后,就变成

  • 本文向大家介绍PHP实现的贪婪算法实例,包括了PHP实现的贪婪算法实例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了PHP实现的贪婪算法。分享给大家供大家参考,具体如下: 背景介绍:贪婪算法与数据结构知识库算法可以说是离我们生活最近的一种算法,人总是贪婪的嘛,所以这种算法的设计是很符合人性的。之所以这么说,是因为人们会在生活中有意无意的使用贪婪算法来解决问题。最常见的就是找零钱了,每个人