算法设计与分析实验四:贪心算法 |
您所在的位置:网站首页 › 实验三贪心算法是什么 › 算法设计与分析实验四:贪心算法 |
一、实验目的 1、深入理解贪心策略的基本思想。 2、能正确采用贪心策略设计相应的算法,解决实际问题。 3、掌握贪心算法时间空间复杂度分析,以及问题复杂性分析方法 二、问题描述 假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 算法设计:对于给定的k个待安排的活动,计算使用最少会场的时间表。 输入输入数据的第一行有1 个正整数k(k≤10000),表示有k个待安排的活动。接下来的k行中,每行有2个正整数,分别表示k个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。 输出输出一个整数,表示最少会场数。 数据结构数据的逻辑结构:数组begin[1000],end[1000] 物理存储结构:顺序存储结构 数据的基本操作:查找,遍历 六、算法设计 #include using namespace std; int main() { int k; cin >> k; int begin[1000]; //记录会议的开始时间 int end[1000]; //记录会议的结束时间 for(int i=0;i > begin[i] >> end[i];} sort(begin,begin+k); //排序,最早开始时间 sort(end,end+k); //排序,最早结束时间 int count=0,j=0; for(int i=0;i end[j])j++; //说明可以当前最早结束的场馆内可以容纳下一个活动,j++更新下一个最早结束点 else count++;//需要多一个场馆 } cout |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |