算法实验指导书(上交版)

《算法实验指导书(上交版)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《算法设计与分析》实验指导书实验一川贪心方法解背包M题一：实验目的掌握按贪心方法原理求背包问题最优解的方法二:问题描述背包问题描述如下：己知背包容量M=120物品种类数n=10各种物品的总效益pi(i=U,10):50,60,70,80,90,80,70,60,50,40各种物品的总重量wi(i=l,210):17,30,25,41,80,70,64,56,47,38求：各种物品所収重量占其总重量的比例xi(i=l,2,.....10)，满足0<=1<=1，且口/士z门〉Wixi<=M且使得$+达到最

2、#直.§一’三.基本要求'(1)按三种不同的量度标准分別计算所得最大总效益，然后比较哪个最大1.按效益值由大到小取物品.2.按重量值由小到大取物品3.按比值pi/wi的伉巾大到小取物品四：选做题装箱问题问题描述：装箱问题可简述如下：设有编号为0、1、…、n-1的n种物品，体积分别为vO、vl、…、vn-lo将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，即对于0

3、物品的集合分划成n个或小于n个物品的所有子集，最优解就可以找到。但所有可能划分的总数太大。对适当大的n,找出所有可能的划分要花费的时间是无法承受的。为此,对装箱问题采用非常简单的近似算法，即贪婪法。该算法依次将物品放到它第一个能放进去的箱子屮，该算法虽不能保证找到最优解，但还是能找到非常好的解。不失一般性，设n件物品的体积是按从大到小排好序的，即有vO多如不满足上述要求，只要先对这n件物品按它们的体积从大到小排序，然后按排序结果对物品重新编号即可。装箱算法简单描述如下：{输入箱子的容积；输入物品种数n;

4、按体积从大到小顺序，输入各物品的体积；预置己用箱子链为空；预置已用箱子计数器box_COunt为0;for(i=0;i

5、100个单位体积。按上述算法计算，需三只箱子，各箱子所装物品分别为：第一只箱子装物品1、3;第二只箱子装物品2、4、5;第三只箱子装物品6。而最优解为两只箱子，分别装物品1、4、5和2、3、6。若每只箱子所装物品用链表来表示，链表首结点指针存于一个结构中，结构记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。实验二求图的任两结点间的距离—:实骑0的掌握按动态规划原理解决计算图的任两结点间的距离的Floyd算法二:问题描述设图G的结点个数n=10,给定一个10*10矩阵作为图G

6、的成本矩阵.其中的元素99相当于无穷，表示相应的两个结点间没有边相连09987654321I990998765432899099876543789909987654c=67899099876556789909987645678990998734567899099823456789909912345678990三.基本要求(1)算法采用三重循环。(2)显示结果要清晰易懂(3)本题运行结果实验三流水线调度问题一：实验目的掌握按动态规划原理求解一类特定条件下的流水线调度问题具体做法.二:问题描述己知作业个数n

7、=10各个作业第一道工序所须时间ai(I=1,2......，n)各个作业第二道工序所须时间bi(I=l，2......，n)作业序号：12345678910a;25b;21303540453141516150556065703949596979规定：(1)任一个作业必须先做完第一道工序才能做第二道工序(1)任一个作业的任一道工序必须连续做完，才能屮断而让别的作业做完.求：一种最优调度方案，即使总的完成时间最短的调度方案，用长度为n的一维数组s表示，使s[il为按先后次序排在第H位进行处理的作业的序号.

8、(1)用一个4*20的二维数组M,第1行存放按从小到大排序的20个所给出的ai和bi,第2行存放相应的作业序号，第3行存放1或2(1代表是來自ai，2代表是來自bi)，第4行存放0或1(0代表作业序号未进入最优调度方案；1代表作业序号己进入最优调度方案)(2)排序完后，按课本所述方法求一种最优调度方案，存放在S中。四.选做题矩阵的斯特拉斯森乘法闷题描述给定两个4阶方阵A和B，试用把每个方阵分割成4个2阶方阵，然后采用斯特拉斯森乘法，求A乘以