华东师范大学计算机科学技术系上机实践报告

《华东师范大学计算机科学技术系上机实践报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华东师范大学计算机科学技术系学生上机实践报告华东师范大学计算机科学技术系上机实践报告课程名称：算法设计与分析年级：08上机实践成绩：指导教师：柳银萍姓名：朱丽辉上机实践名称：贪心算法学号：10082130133上机实践日期：2010-5-31上机实践编号：NO.5组号：上机实践时间：15:00-16:30一、目的二、内容与设计思想1.若在0-1背包问题中各物品是依重量递增排列时，其价值恰好依递减序排列。对这个特殊的0-1背包问题，请设计一个有效算法找出最优解。要求：输入：第一行输入一个数n，表示有n种物品；接下来一行输入n个数表示这n个物品的

2、重量；接下来一行输入n个数表示这n个物品的价值；最后一行输入一个数字c表示背包容量输出：输出2行，第一行是该背包装入得最大价值，第二行有n个数，0表示不被选，1表示被选1.1其思路是：将n件物品的价值/重量比求出（价值/重量比，也就是单位重量物品的价值），然后按照非递增排序。装入过程，从价值/重量比最大的物品开始装入，直到某一件物品不能全部装入背包的时候，停止装入，而要对最后一件不能全部装入的物品进行部分装入，将背包装满，总价值达到最大1.2具体算法是：首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最

3、高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止2.设计贪婪算法，求解课件中的二分图覆盖问题。要求：输入：第一行是A中元素个数m，接下来2m行是A中每个元素的情况，其中第一行是元素的顶点A[i]以及它与B中相连顶点的个数New[A[i]]，第二行是New[A[i]]个B中元素；第2m+2行是B中元素个数n，最后一行是n个B中元素第8页共8页华东师范大学计算机科学技术系学生上机实践报告输出：一行输出A¢中的各个元素2.1其思路是：

4、二分图覆盖问题符合最优子结构性质，我们可以用贪心算法来求解。每次把能覆盖未被覆盖的顶点数目最多的顶点加入A¢。2.2具体算法是：•m＝0;//当前覆盖的大小•对于A中的所有i，New[i]=Degree[i]•对于B中的所有i，Cov[i]=false•while(对于A中的某些i，New[i]>0){•设v是具有最大的New[i]的顶点；•C[m++]=v;•for(所有邻接于v的顶点j){•if(!Cov[j]){•Cov[j]=true;•对于所有邻接于j的顶点，使其New[k]减1}}}•if(有些顶点未被覆盖)失败else找到一个覆

5、盖3．一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n(n<=5000)和k(k<=1000)个加油站位置，编程计算最少加油次数。并证明算法能产生一个最优解。要求：输入：第一行有2个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。输出：输出编程计算出的最少加油次数。如果无法到达目的地，则输出”NoSol

6、ution”。3.1其思路是：该题目求加油最少次数，即求最优解的问题，我们可以用贪心算法来求。可分成几个步骤，一般来说，每个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。3.2具体算法是：对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3……n   1.始点到终点的距离小于n，则加油次数k=0；   2.始点到终点的距离大于n，   A 加油站间的距离相等，即ａ[i]=a[j]=L=n，则加油次数最少k=n；第8页共8页华东师范大学计算机科学技术系学生上机实践

7、报告   B 加油站间的距离相等，即ａ[i]=a[j]=L>n，则不可能到达终点；C 加油站间的距离相等，即ａ[i]=a[j]=L

8、由于（b[1],b[2],……b[n]）是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b[1]=1,则（b[2],b[3],…