贪心算法和随机算法 第五章 试验报告

1、实验报告实验目的： 理解和掌握贪心算法和随机算法的思想。实验内容：通过解决几个实际例子，来理解和加深对贪心算法以及随机算法的应用。实验过程：1.背包问题 1.1问题描述 有一个背包，背包的容量是150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。1.2算法分析 因为物品可以任意分割，所以可以计算每件物品的单位质量的价值，然后从大到小排序，然后从序列中价值最高的第一个物品开始选起，在保证载容范围内，直到装不下第i个整个物品时， 则计算余留空间的容量，得到此物体应分割多少装进去。1.3程序框图物品ABCDEFG重量35306050401025价值1

2、0403050354030单位价值0.285741.333330.500001.000000.875004.000001.20000顺序7264513装入的物品为：F(10),B(30),G(25),D(50),E(35) 40 + 40 + 30 + 50+ 0.875*35=190.631.4程序源代码/-背包问题#includestdio.h#define N 7#define C 150float weight7;float value7;float pervalue7;int n,a7;float max=0;void readdata()int i;for(i=0;iN;i+)sc

3、anf(%f,&weighti);for(i=0;iN;i+)scanf(%f,&valuei);for(i=0;iN;i+)pervaluei=valuei/weighti;/ printf(%f ,pervaluei);for(i=0;iN;i+)ai=i;void sort()int i,j,t;for(i=0;iN;i+)for(j=i+1;jpervalueai)t=ai;ai=aj;aj=t;float search()int i,j; float con,val; for(i=0;iN;i+)con=weightai;val=valueai;for(j=i+1;jN;j+)if(

4、weightaj(C-con) con+=weightaj; val+=valueaj;else val=val+(pervalueaj)*(150-con);con=150;if(maxval)max=val;/printf(n%f,max);return (max);void main()int i;float v; scanf(%d,&n);for(i=0;in;i+)max=0; readdata(); sort(); v=search();printf(%.2fn,v);2. 照亮的山景2.1问题描述在一片山的上空，高度为T处有N个处于不同位置的灯泡，如图。如果山的边界上某一点于某灯

5、i的连线不经过山的其它点，我们称灯i可以照亮该点。开尽量少的灯，使得整个山景都被照亮。山被表示成有m个转折点的折线。2.2算法思想照亮整个山景相当于照亮每一个转折点。可对每个凹点画向上方的延长线，交于高度线，从而得到每一个凹点被照到时灯所放置的范围区间，然后以每个区间的后端点由小到大排序。然后对于排好序的区间，检查其后点所能同时找到的区间，并标记。知道所有的区间都被标记完，即说明所有的凹点被照到，也就是整个山景被照亮。2.3程序框图1322.4程序源代码#include stdio.hint M,N;int b100;float left,right,x100,y100,qian50,hou5

6、0,top=40.0;void readdata()int i;printf(输入折点的个数：);scanf(%d,&M);printf(输入每个折点的坐标：);for(i=0;iM;i+)scanf(%f%f,&xi,&yi);left=-9999;/设置左端无穷远点right=9999;/设置右端无穷远点creatqujian()/创建区间int i;int num=0;for(i=1;iyi|yi+1yi)/判断为凹点qiannum=(xi-1-xi)*(top-yi)/(yi-1-yi)+xi;if(qiannumxi) qiannum=left; /求得左端点hounum=(xi+1

7、-xi)*(top-yi)/(yi+1-yi)+xi;if(hounumxi) hounum=right; /求得左端点num+; /统计区间的个数。return (num);void sortqujian()/对区间按右端点由小到大排序int i,j,t;for(i=0;iN;i+)bi=i;/排序辅助数组for(i=0;iN;i+)for(j=i+1;jN;j+)if(houjhoubi)t=houj;houj=houbi;houbi=t;int search()int i,j;int num=0,tag=0; int used100=0; for(i=0;iN;i+) /对于排好序的区间

8、，检查其后点所能同时找到的区间，并标记 if(!usedbi) for(j=i+1;jN;j+) if(!usedbj&qianbj=N)break; / printf(%dn,num); return (num);void main()int num=0;int spot;readdata();N=creatqujian();sortqujian();spot=search();printf(%dn,spot);3. 搬桌子问题3.1问题描述某教学大楼一层有n个教室，从左到右依次编号为1、2、n。现在要把一些课桌从某些教室搬到另外一些教室，每张桌子都是从编号较小的教室搬到编号较大的教室，每一

9、趟，都是从左到右走，搬完一张课桌后，可以继续从当前位置或往右走搬另一张桌子。输入数据：先输入n、m，然后紧接着m行输入这m张要搬课桌的起始教室和目标教室。输出数据：最少需要跑几趟。3.2算法思想贪心算法，把课桌按起点从小到大排序，每次都是搬离当前位置最近的课桌。3.3程序框图例如：1 2 3 4 5 6 7 8 9 101 3 3 9 4 6 6 10 7 83.4程序源代码#includeint N;int b100;structint start;int end;a100;void sort(int n)int i,j,t;for(i=0;in;i+)bi=i;for(i=0;in;i+)

10、for(j=i+1;jn;j+)if(aj.startabi.start)t=bi;bi=bj;bj=t;int search()int i;int n,m,min,num,temp,used100=0;scanf(%d%d,&m,&n);for(i=0;in;i+)scanf(%d%d,&ai.start,&ai.end);sort(n); /按start从小到大对数组a排序min=0;num=0;while(numn)temp=0;for(i=0;i=temp)temp=abi.end;usedbi=1;num+;min+;printf(%dn,min); return (min);void main()int i,tang;scanf(%d,&N);for(i=0;iN;i+)tang=search();实验总结：1.本次的试验较为简单