1、华东师范大学计算机科学技术系学生上机实践报告第 1 页 共 9 页华东师范大学计算机科学技术系上机实践报告课程名称： 算法设计与分析 年级：08 上机实践成绩：指导教师： 柳银萍 姓名：朱丽辉上机实践名称：贪心算法 学号：10082130133 上机实践日期：2010-5-31上机实践编号：NO.5 组号： 上机实践时间：15:00-16:30一、目的二、内容与设计思想1. 若在 0-1 背包问题中各物品是依重量递增排列时，其价值恰好依递减序排列。对这个特殊的 0-1 背包问题，请设计一个有效算法找出最优解。要求：输入：第一行输入一个数 n，表示有 n 种物品；接下来一行输入 n 个数表示这
2、n 个物品的重量；接下来一行输入 n 个数表示这 n 个物品的价值；最后一行输入一个数字 c 表示背包容量输出：输出 2 行，第一行是该背包装入得最大价值，第二行有 n 个数，0 表示不被选，1 表示被选 1.1 其思路是：将 n 件物品的价值/重量比求出（价值/重量比，也就是单位重量物品的价值），然后按照非递增排序。装入过程，从价值/重量比最大的物品开始装入，直到某一件物品不能全部装入背包的时候，停止装入，而要对最后一件不能全部装入的物品进行部分装入，将背包装满，总价值达到最大 1.2 具体算法是：首先计算每种物品单位重量的价值 Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高
3、的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过 C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止2. 设计贪婪算法，求解课件中的二分图覆盖问题。要求：输入：第一行是 A 中元素个数 m，接下来 2m 行是 A 中每个元素的情况，其中第一行是元素的顶点 Ai以及它与 B 中相连顶点的个数 NewAi，第二行是 NewAi个 B 中元素；华东师范大学计算机科学技术系学生上机实践报告第 2 页 共 9 页第 2m+2 行是 B 中元素个数 n，最后一行是 n 个 B 中元素输出： 一行输出 A中的各个元素2.1 其思路是： 二分图覆
4、盖问题符合最优子结构性质，我们可以用贪心算法来求解。每次把能覆盖未被覆盖的顶点数目最多的顶点加入 A。2.2 具体算法是： m0; /当前覆盖的大小 对于 A 中的所有 i，Newi=Degreei 对于 B 中的所有 i，Covi=false while(对于 A 中的某些 i，Newi0) 设 v 是具有最大的 Newi的顶点； Cm+=v; for(所有邻接于 v 的顶点 j) if(!Covj) Covj = true; 对于所有邻接于 j 的顶点，使其 Newk减 1 if(有些顶点未被覆盖 ) 失败else 找到一个覆盖3一辆汽车加满油后可行驶 n 公里。旅途中有若干个加油站。设计
5、一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的 n(n n，则不可能到达终点；C 加油站间的距离相等，即i=aj=L#define MAX 100int max(int i,int j)华东师范大学计算机科学技术系学生上机实践报告第 4 页 共 9 页return(i=j) ?i:j;int min(int i,int j)return(i0)? 1:0;for(i=0;i#define max 50int Max(int s)/求出 Newi中的最大顶点 kint i,k=0,t,n=0;for(i=0;i=t)t=si;k=i;return k;void erfe
6、n(int A,int B,int New, int degreemaxmax,int m,int n )/degreeij是 A 中第 i+1 个元素与 B 中相连元素中的第 j+1 个 int s,cmax,NEWmax,k=0,covmax,i,g,j,v,h=0;for(i=0;i#define max 1000int add(int a,int m,int n) int i,s=0;for(i=m+1;in)m=j;cj=1;b=Y;else b=N; else /间距不相等 int m=0,term=0;for(i=1;in)term+;if(term!=0)b=N;华东师范大学计算机科学技术系学生上机实践报告第 8 页 共 9 页elsefor(j=1;jn)m=j;cj=1;b=Y; if(b=Y)for(i=1;i=k;i+)if(ci!=0)h+;printf(“%dn“,h);else printf(“NoSolutionn“);void main()int i,n,k,amax;scanf(“%d%d“,a0=0;for(i=1;i=k+1;i+)scanf(“%d“,jiayou(n,k,a);运行结果:要求至少给出 1 组测试数据运行结果。华东师范大学计算机科学技术系学生上机实践报告第 9 页 共 9 页
