九脉堂是做网站的,龙南建设局网站,目前做网站,软件网站模板实验二#xff1a;贪心算法
【实验目的】
应用贪心算法求解活动安排问题。
【实验性质】
验证性实验。
【实验要求】
活动安排问题是可以用贪心算法有效求解的很好的例子。
问题#xff1a;有n个活动的集合A{1,2,…,n}#xff0c;其中每个活动都要求使用同一资源贪心算法
【实验目的】
应用贪心算法求解活动安排问题。
【实验性质】
验证性实验。
【实验要求】
活动安排问题是可以用贪心算法有效求解的很好的例子。
问题有n个活动的集合A{1,2,…,n}其中每个活动都要求使用同一资源如演讲会场等而在同一时间内只有一个活动能使用这一资源。
求解安排尽量多项活动在该场地进行即求A的最大相容子集。
设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下 i 1 2 3 4 5 6 7 8 9 10 11 s[i] 1 3 0 5 3 5 6 8 8 2 12 f[i] 4 5 6 7 8 9 10 11 12 13 14
将此表数据作为实现该算法的测试数据。
【算法思想及处理过程】 1.定义了活动结构体Activity包含活动的名称name、开始时间start和结束时间end。 2定义了比较函数compare用于按照活动的结束时间升序排序。 3定义了一个活动安排函数activityArrangement接受一个活动数组和活动个数作为参数并按照活动结束时间排序后进行活动安排。 4在活动安排函数中首先使用sort函数对活动数组进行排序排序规则是使用之前定义的比较函数compare。 5输出第一个活动的信息。 6初始化一个变量lastEnd用于记录最后一个加入最大相容子集的活动的结束时间。 7遍历剩下的活动数组如果当前活动的开始时间晚于等于lastEnd即活动不与已加入的活动冲突将该活动加入最大相容子集并更新lastEnd为该活动的结束时间。 8输出结果。 在主函数中首先获取用户输入的活动个数然后根据输入的活动个数循环获取活动的名称、开始时间和结束时间。最后调用活动安排函数(activityArrangement)进行活动安排。 【程序代码】 #include iostream #include algorithm using namespace std; struct Activity { int name; int start; int end; }; bool compare(Activity a, Activity b) { return a.end b.end; } void activityArrangement(Activity activities[], int n) { sort(activities, activities n, compare); cout 结果为 endl; cout Activite activities[0].name activities[0].start , activities[0].end endl; int lastEnd activities[0].end; for (int i 1; i n; i) { if (activities[i].start lastEnd) { cout Activite activities[i].name activities[i].start , activities[i].end endl; lastEnd activities[i].end; } } cout endl; } int main() { int n; cout 请输入活动个数: ; cin n; Activity activities[50]; for (int i 0; i n; i) { cout 请输入第i1次活动信息名称 开始时间 结束时间 : ; cin activities[i].name activities[i].start activities[i].end; } activityArrangement(activities, n); return 0; } 【运行结果】
自行运行截图 【算法分析】 排序算法的时间复杂度使用了STL的sort函数对活动数组进行排序该函数的时间复杂度为 O(nlogn)其中n为活动个数。 遍历活动数组的时间复杂度在活动安排函数中遍历了剩下的活动数组时间复杂度为 O(n)其中n为活动个数。 综上代码的时间复杂度为 O(nlogn n)即 O(nlogn)。
