贪心算法求解区间覆盖问题.docx

算法分析与设计试验报告第5次试验区间掩盖时间4. 28下午地点软件大楼109试验名称贪心算法求会场支配问题试验目的通过上机试验，要求把握贪心算法的思想，解决会场支配的问题并且实 现。试验原理贪心算法重要的两共性质：贪心选择性质和最优子结构性质。从问题的某一个初始解动身逐步靠近给定的目标，以尽可能快的地求得更好 的解。当达到某算法中的某一步不能再连续前进时，算法停止。1 .建立数学模型来描述问题。2 .把求解的问题分成若干个子问题。3 .对每一子问题求解，得到子问题的局部最优解。4 .把子问题的解局部最优解合成原来解问题的一个解。在这个试验当中，将会场的开头和结束的时间都用vector向量来表示， 然后将将开头的值用bool变量表示，开头时间是true,结束时间是false,依 次检索,运用推断语句 if (i=nTxi. t<xi+l. t) && cur>max)对这些会议的时间进行推断，然后看是否需要添加会议室；再在进行推断；试验步骤步骤如下：1、首先定义数据结构：以时间为核心，定义结构体point,它拥有两个属性， t是时间，f表示是开头时间还是结束时间；2、对全部对象按时间大小排序；3、依次计算，假如是开头时间则count+,假如是结束时间则count-,其中 最大的count即是最少的会场数。count表示目前开头且未结束的活动数；struct point(int t;bool f;);bool cmp(point x,point y)(return x. t<y. t;)关键代码int greedy(vector<point> x)(int max=0, cur=0, n二x. size ();sort (x. begin (), x. end (), cmp);for(int i=0;in;i+)(if (xi. f)cur+;elsecur;if (i=n-l | xi. t<xi+l. t) && curmax)处理 xi=xi+l 的状况max=cur;当 cur>max 且xi=xi+l时，i时间确定是开头时间，i + 1时间可能是开头时间，也可能是结束时间假如是结束时间，说明某活动开头时间和结束时间相同，不需要会场，故不对max更新;假 如是开头时间，那在i+1次更新max效果一样returnmax;因此i次不进行更新测试结果 3 E:学习'算法分析与没计实验课第五次实验课'会场安排问爱l.exe.n叫Tg51 2312 2825 35 2? 8036 503.一 一试验心得关于运用贪心算法来球会议场地的问题，这个问题主要是需要计算的是上一个 会场的结束时间与下一个会场的开头时间会不会重合，所以在这里我奇妙的运 用了 vector向量来表示会议的开头于结束的时间，然后依据bool来检索会议 的开头于结束时间，然后推断是否时间重合，然后再来推断是否需要再添加会 议室，在这个试验中最奇妙的还是要运用vector函数来推断，所以试验的过 程中需要我们精密的思索问题，将问题简化才是最重要的。试验得分助教签名附录：完整代码/4d5贪心算法单源最短路径问题ttinclude <iostream>ttinclude <fstream>ttinclude <string>using namespace std;const int N = 5;const int M = 1000;ifstream fin(“4d5 txt");template<class Type>void Di jkstra(int n, int v, Type dist , int prev, Type cN+l);void Traceback(int v, int i, int prev);输出最短路径 v 源点,i 终点int main ()int v = 1;源点为 1 .int dist N+l, prevN+l, cN+l N+l;cout«有向图权的矩阵为："«endl;for (int i=l; i<=N; i+)(for (int j=l; j<=N; j+)(fin»ci j;cout«ci Ej«z")cout«endl;)Di jkstra(N, v, dist, prev, c);for (int i=2; i<=N; i+)(cout<<"源点1到点"*i«的最短路径长度为:其路径为;Traceback(l, i, prev);cout«endl;return 0;template<class Type> void Di jkstra(int n, int v, Type dist , int prev, Type cN+l)(bool sN+l;.for (int i=l; i<=n; i+)(disti = cv i表示当前从源到顶点i的最短特别路径长度si = false;if(disti = M)(previ = 0;纪录从源到顶点i的最短路径i的前一个顶点)else(previ = v;)distv = 0;v = true; 源到本身的距离是0；for(int i=l; i<n; i+)int temp = M;int u = v; 上一顶点取出V-S中具有最短特别路径长度的顶点u for (int j=l; j<=n; j+)(if(!sj) && (distj<temp)temp = distj;su = true;依据作出的贪心选择更新Dist值for (int j=l; j<=n; j+)(if(!sj) && (cu j<M)Type newdist = distu + cuj;if(newdist < distj)dist j = newdist;prevj = u;)输出最短路径V源点，i终点void Traceback(int v, int i, int prev 口)(if (v = i)(cout«i;return;)Traceback(v, previ, prev);cout«"->"«i;会场支配问题（贪心算法）/input, txt/5 /I 23/12 28/25 35/27 80/36 50/output.txt/3ttinclude <iostream>ttinclude <vector>ttinclude <algorithm>using namespace std;struct point(int t;bool f;);bool cmp(point x,point y)(return x. t<y. t; int greedy(vector<point> x)int max=O, cur=O, n=x. size();sort (x. begin (), x. end (), cmp);for (int i=0;i<n;i+)(.if (xi. f)cur+;elsecur；if (i=n-l | | xi. t<xi+l. t) && cur>max)处理 xi=xi+l的状况max=cur;当 cur>max 且 xi=xi+l时,i时间确定是开头时间，i+1时间可能是开头时间，也可能是结束时间假如是结束时间，说明某活动开头时间和结束时间相同，不需要会场，故不对max更新;假如是开头时间，那在i+1次更 新max效果一样max;return因此i次不进行更新int main ()vector<point> x;int n, i;point temp;while (cin»n, n)for(i=0;i<n;i+)姓名杨玉茹学号202208010325班级计科1503时间4. 28下午地点软件大楼109试验名称贪心算法求解区间掩盖问题试验目的通过上机试验，要求把握贪心算法的思想，解决区间掩盖的问题并且实 现。试验原理贪心算法重要的两共性质：贪心选择性质和最优子结构性质。从问题的某一个初始解动身逐步靠近给定的目标，以尽可能快的地求得更好 的解。当达到某算法中的某一步不能再连续前进时，算法停止。在这个试验当 中，需要运用最少的k数来掩盖题目中所给的区间，因此我们只需要计算出这 个区间的长度，依次与坐标进行比较，然后每加了一个k,那么就纪录下来， 运用贪心算法的核心思想，因此我们就可以得到最终需要的k的数目了。试验步骤步骤如下：1.首先将所给出的坐标进行排序，然后命名一个标尺max来推断是否达到了所 给的坐标，依次增加max的值，直到最终一个坐标值；关键代码if (ai>ajl) t=ai ;ai=aj ;aj=t;)max=k+aO;for (i=l;in;i+)if(max<ai)temp. f=true;cin»temp. t;x. push_back (temp);temp. f=false;cin»temp. t;x. push_back (temp);)cout<<greedy (x) «endl;x. clear ();)return 0;区间掩盖问题#include<iostream>#include<iomanip>using namespace std;int main()int n, k, i, j, aElOOOO, t, max, sum=l;cin»n»k;for(i=0; i<n; i+)cin»ai;for(i=0;i<n;i+) for(j=i+l;j<n;j+)if (ai>aj) t=ai ;ai=aj ;aj=t;)max=k+aO;for(i=l;i<n;i+)(if(max<ai) max=ai+k;,sum+;.)cout«sum«endl;return 0; max=ai+k;SUD1+;)测试结果3 E:学习、算法分析与没计实给课逢五次实验课'区间蔡美问题Lexe 口 |回|目!5 31 3 8 5 113Process exited after 21.04 seconds with return ualue 0请按任意键继续.试验心得关于运用贪心算法来求区间掩盖的问题，其实这个问题和会议场地的问题是类 似的，依次用k来衡量是否达到了最终一个坐标值，假如没有达到，那么我们 就加k,依次进行计数，所以这个过程中最重要的就是运用了贪心算法的核心 思想。试验得分助教签名算法分析与设计试验报告第5次试验最短路径姓名杨玉茹学号202208010325班级计科1503时间4. 28下午地点软件大楼109试验名称贪心算法求最短路径试验目的通过上机试验，要求把握贪心算法的思想，采用Dijkstra算法求解最短 路径并实现。试验原理Dijkstra算法是解单源最短路径问题的贪心算法。基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶 点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含 有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从 源到u的特别路径，并用数组dist纪录当前每个顶点所对应的最短特别路径 长度。Dijkstra算法每次从V-S中取出具有最短特别路长度的顶点u,将u 添加到S中，同时对数组dist作必要的修改。一旦S包含了全部V中顶点， dist就纪录了从源到全部其他顶点之间的最短路径长度。Dijkstra算法可描述如下，其中输入带权有向图是G=(V,E), V=1,2,， n),顶点v是源。c是一个二维数组，表示边(i, j)的权。当(i,j)不 属于E时，ci j是一个大数。disti表示当前从源到顶点i的最短特别路 径长度。在Dijkstra算法中做贪心选择时，实际上是考虑当S添加u之后， 可能消失一条到顶点的新的特别路，假如这条新特别路是先经过老的S到达顶 点u,然后从u经过一条边直接到达顶点i,则这种路的最短长度是 distu+cu i。假如 distu+cu i<disti,则需要更新 disti的值。试验步骤步骤如下：(1)用带权的邻接矩阵c来表示带权有向图，表示弧<vi,vj上的 权值。设S为已知最短路径的终点的集合，它的初始状态为空集。从源点V经 过S到图上其余各点Vi的当前最短路径长度的初值为:disti=cvi, vi 属于V.(2)选择 vu,使得 dist u=Mindist ivi 属于 V-S, vj 就是长度最短的最短路径的终点。令S二S U u.(3)修改从v到集合V-S上任一顶点vi的当前最短路径长度:假如 distu+cu j< distj则修改 distj= distu+cu j.(4)重复操作(2), (3)共n-l次.关键代码template<class Type>void Dijkstra(int n, int v,Type dist, int prev,Type cN+l)bool sN+l;for (int i=l; i<=n; i+)(disti - cv i ;disti表小当前从源到顶点i的最短特别路 径长度si= false;if (disti = M)(previ二0;纪录从源到顶点i的最短路径i的前一个顶点else(previ = v;)dist v = 0;sv=true; 源到本身的距离是0；for(int i=l; i<n; i+)int temp = M;int u=v;上一顶点取出V-S中具有最短特别路径长度的顶点u for(int j=l; j<=n; j+)(if(!sj) && (distj<temp)(U = j；temp = dist j;)su = true;依据作出的贪心选择更新Dist值for(int j=l; j<=n; j+)(if(!sj) && (cuj<M)(Type newdist = distu + cuj;测试结果试验心得if(newdist < distj)(dist j = newdist;prevj = u;E:学习算法分析与没计实验第第五次实验黑单元最短路径exe有向图权的矩阵为：6885240 0 4234416 2293292 4674752 1979550933 175057032 -2 1979453794 4232397K度力迅其路径为七% 度为"91899450,其路径为1->3eu- 甘咯泽为45径为1->5源点1到点4的曩短皤径长度为:2293252,其粮宜 源点1到点5的取短路径长度为：1979446784,其由Process exited after 0.5235 seconds with return value 0 请按任意键继续.关于运用贪心算法求解单源最短路径的问题，其实Dijkstra算法就是一个贪 心算法，但是由于求单源最短路径是一个过程比较简单的问题，而且这个算法 也实质上是一个广度优先算法，所以在进行比较的时候，思维就会变得比较混 乱，但是可以讲二将这些比较的步骤也许分为两个步骤，首先从源点v经过S 到图上其余各点vi的当前最短路径长度的初值为：disti=cvi, vi属 于V.假如某个元素被纳入源点的时候，那么相应的Si就为true；然后再修改从V到集合V-S上任一顶点vi的当前最短路径长度：假如 distu+cu j< distj则修改 distj= distu+cu j,依次进行循 环即可，所以其实在最开头将思路理清，那么我们就可以进行写代码了。姓名杨玉茹学号OAQOAOA no Q r班级计科1503试验得分助教签4zOzzOol) LOozb 7算法分析与设计试验报告第5次试验会场支配