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

2024-09-30 08:59:45

本文所述算法即假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有活动。采用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语言使用回溯法解旅行售货员问题与图的m着色问题

旅行售货员问题 1.问题描述: 旅行售货员问题又称TSP问题,问题如下:某售货员要到若干个城市推销商品,已知各城市之间的路程(或旅费),他要选定一条从驻地出发,经过每个城市一遍最后回到驻地的路线,使总的路线(或总的旅费)最小.数学模型为给定一个无向图,求遍历每一个顶点一次且仅一次的一条回路,最后回到起点的最小花费. 2.输入要求: 输入的第一行为测试样例的个数T( T < 120 ),接下来有T个测试样例.每个测试样例的第一行是无向图的顶点数n.边数m( n < 12,m < 100 )
C++实现八皇后问题的方法

本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法.分享给大家供大家参考之用.具体方法如下: 一般在八皇后问题中,我们要求解的是一个8*8的国际象棋棋盘中,放下8个皇后且互相不能攻击的排列总数.皇后的攻击范围为整行,整列,以及其斜对角线. 由于皇后的攻击范围特性,注定我们每行只能放下一个皇后,于是我们要做的只是逐行放下皇后.八皇后问题是回溯法的典型问题.这里我们用的方法很简单: 从第一行开始逐个检索安全位置摆放皇后,一旦有安全位置则考虑下一行的安全位置.如果发现某行没
C++基于回溯法解决八皇后问题示例

本文实例讲述了C++基于回溯法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯:否则,进入该子树,继续按深度优先策略搜索. 回溯法指导思想--走不通,就掉头.设计过程:确
C++三色球问题描述与算法分析

本文实例讲述了C++三色球问题.分享给大家供大家参考,具体如下: /* * 作者:刘同宾 * 完成日期:2012 年 11 月 15 日 * 版本号:v1.0 * * 输入描述: * 问题描述:三色球问题:若一个口袋中放有12个球,其中有3个红的.3个白的和6个黒的,问从中任取8个共有多少种不同的颜色搭配? * 提示: 设任取的红球个数为i,白球个数为j,则黒球个数为8-i-j,根据题意红球和白球个数的取值范围是0~3, * 在红球和白球个数确定的条件下,黒球个数取值应为8-i-j<=6.
八皇后问题的相关C++代码解答示例

八皇后问题即指在一个8*8的棋盘上放置8个皇后,不允许任何两个皇后在棋盘的同一行.同一列和同一对角线上.关键字:递归.上溯.通用技巧: 经观察发现,对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7) 其主对角线(即左上至右下)上的每个点的i-j+7的值(范围在(0,14))均相等: 其从对角线(即右上至左下)上的每个点的i+j的值(范围在(0,14))均相等: 且每个主对角线之间的i-j+7的值均不同,每个从对角线之间的i-j+7的值亦不同: 如a[3][4]: 主:3-4+7
c++递归实现n皇后问题代码(八皇后问题)

还是先来看看最基础的8皇后问题: 在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 扩展到N皇后问题是一样的.一看,似乎要用到二维数组.其实不需要.一维数组就能判断,比如Arr[i],就可以表示一个元素位于第i行第Arr[i]列--应用广泛的小技巧.而且在这里我们不用考虑去存储整个矩阵,如果Arr[i]存在,那么我们在打印的时候,打印到皇后位置的时候输出1,非皇后位输出0即可. 这种思路的实现方式网上大把,包括前面提到的那
基于C++的农夫过河问题算法设计与实现方法

本文实例讲述了基于C++的农夫过河问题算法设计与实现方法.分享给大家供大家参考,具体如下: 问题描述: 一个农夫带着-只狼.一只羊和-棵白菜,身处河的南岸.他要把这些东西全部运到北岸.他面前只有一条小船,船只能容下他和-件物品,另外只有农夫才能撑船.如果农夫在场,则狼不能吃羊,羊不能吃白菜,否则狼会吃羊,羊会吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不吃白菜.请求出农夫将所有的东西运过河的方案. 实现上述求解的搜索过程可以采用两种不同的策略:一种广度优先搜索,另一种
C++回溯法实例分析

本文实例讲述了C++的回溯法,分享给大家供大家参考之用.具体方法分析如下: 一般来说,回溯法是一种枚举状态空间中所有可能状态的系统方法,它是一个一般性的算法框架. 解向量a=(a1, a2, ..., an),其中每个元素ai取自一个有限序列集Si,这样的解向量可以表示一个排列,其中ai是排列中的第i个元素,也可以表示子集S,其中ai为真当且仅当全集中的第i个元素在S中:甚至可以表示游戏的行动序列或者图中的路径. 在回溯法的每一步,我们从一个给定的部分解a={a1, a2, ..., ak}开始
java 中模式匹配算法-KMP算法实例详解

java 中模式匹配算法-KMP算法实例详解朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的
JavaScript算法系列之快速排序（Quicksort）算法实例详解

"快速排序"的思想很简单,整个排序过程只需要三步: (1)在数据集之中,选择一个元素作为"基准"(pivot). (2)所有小于"基准"的元素,都移到"基准"的左边:所有大于"基准"的元素,都移到"基准"的右边. (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止. 举例来说,现在有一个数据集{85, 24, 63, 45,
Java 选择排序、插入排序、希尔算法实例详解

1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu
Java 归并排序算法、堆排序算法实例详解

基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组
KMP 算法实例详解

KMP 算法实例详解 KMP算法,是由Knuth,Morris,Pratt共同提出的模式匹配算法,其对于任何模式和目标序列,都可以在线性时间内完成匹配查找,而不会发生退化,是一个非常优秀的模式匹配算法. 分析:KMP模板题.KMP的关键是求出next的值.先预处理出next的值.然后一遍扫过.复杂度O(m+n) 实例代码: #include<stdio.h> #include<string.h> #define N 1000005 int s[N]; int p[N]; int n
KnockoutJS数组比较算法实例详解

这篇文章主要介绍了KnockoutJS数组比较算法实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下前端开发中,数组是一种非常有用的数据结构.这篇博客会解释并分析KnockoutJS实现中使用的数据比较算法. 算法的目的 KnockoutJS使用MVVM的思想,view model中的数组元素会对应data model中的数组数据,当用户进行输入或者请求后台时,数组数据会发生变更, 从而带动UI的更新.例如购物车类的页面,用户可以通过点击
python动态规划算法实例详解

如果大家对这个生僻的术语不理解的话,那就先听小编给大家说个现实生活中的实际案例吧,虽然现在手机是相当的便捷,还可以付款,但是最初的时候,我们经常会使用硬币,其中,我们如果遇到手中有很多五毛或者1块钱硬币,要怎么凑出来5元钱呢?这么一个过程也可以称之为动态规划算法,下面就来看下详细内容吧. 从斐波那契数列看动态规划斐波那契数列:Fn = Fn-1 + Fn-2 ( n = 1,2 fib(1) = fib(2) = 1) 练习:使用递归和非递归的方法来求解斐波那契数列的第 n 项代码如下: #
LRU LFU TinyLFU缓存算法实例详解

目录简介一.LRU和LFU算法 LRU算法 LFU算法小结: 二.TinyLFU 三.Window-TinyLFU 简介前置知识知道什么是缓存听完本节公开课,你可以收获掌握朴素LRU.LFU算法的思想以及源码掌握一种流式计数的算法 Count-Min Sketch 手撕TinyLFU算法.分析Window-TinyLFU源码一.LRU和LFU算法 LRU算法 LRU Least Recently Used 最近最少使用算法 LRU 算法的思想是如果一个数据在最近一段时间没有被访
C++插入排序算法实例详解

本文实例为大家分享了C++插入排序算法实例的具体代码,供大家参考,具体内容如下基本思想每次将一个待排序的元素,按其大小插入到已经排好序的子序列的适当位置,知道全部元素插入完成为止. 直接插入排序 1.排序思路 arr[0...i-1]为有序区(刚开始时i=1,有序区只有arr[0]一个元素),arr[i...size]为待排序区,每次将待排序区的第一个元素arr[i]插入到有序区中的适当位置,每趟操作都使有序区增加一个元素,待排序区减少一个元素. 2.排序算法 void InsertSort
Python决策树和随机森林算法实例详解

本文实例讲述了Python决策树和随机森林算法.分享给大家供大家参考,具体如下: 决策树和随机森林都是常用的分类算法,它们的判断逻辑和人的思维方式非常类似,人们常常在遇到多个条件组合问题的时候,也通常可以画出一颗决策树来帮助决策判断.本文简要介绍了决策树和随机森林的算法以及实现,并使用随机森林算法和决策树算法来检测FTP暴力破解和POP3暴力破解,详细代码可以参考: https://github.com/traviszeng/MLWithWebSecurity 决策树算法决策树表现了对象属性和

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

相关推荐

随机推荐