(陈慧南 第3版)算法设计与分析——第6章课后习题答案

1 第六章课后习题 姓名：赵文浩 学号：16111204082 班级：2016 级计算机科学与技术 6-1 设有背包问题实例，7n ，15M ， 016 ,2,3,5,7,1,4,1w ww，物品装 入背包的收益为 016 ,10,5,15,7,6,18,3ppp。求这一实例的最优解和最大 收益。 解析： 1.Step 首先计算所有物品单位重量的收益，并按照非递增次序排列，得： ID pi wi pi wi 4 6 1 6 0 10 2 5 5 18 4 4.5 2 15 5 3 6 3 1 3 1 5 3 1.67 3 7 7 1 2.Step 下面按照/pi wi非增次序依次尝试将物品装入背包： 4 1 15w ，物品 4 可全选，此时剩余载重为 15 1 14 ； 0 214w ，物品 0 可全选，此时剩余载重为 14212； 5 412w ，物品 5 可全选，此时剩余载重为 1248； 2 58w ，物品 2 可全选，此时剩余载重为 8 53 ； 6 13w ，物品 6 可全选，此时剩余载重为3 12 ； 1 32w ，物品 1 可选2 3，此时剩余载重为 0，选择结束。 综上所述，最优解为 016 ,1,2 3,1,0,1,1,1x xx。此时的最大收益为 105 2 3 156 18355.33 。 6-3 设有带时限作业排序实例，7n ， 016 ,3,5,20,18,1,6,30ppp， 2 016 ,1,3,4,3,2,1,2d dd。 给出此实例为输入， 执行函数JS得到的最优解和 最大收益。 解析： 1.Step 将所有作业按照收益的非增次序排列可得： ID pi di 6 30 2 2 20 4 3 18 3 5 6 1 1 5 3 0 3 1 4 1 2 2.Step 依次将作业添加到作业集合 X 中 初始化作业集合为X ； 选择作业 6， 6X 一定是一个可行解； 选择作业 2，则6,2X 。将其按照期限di非减次序排列可得： ID di 6 2 2 4 -101234 作业6 作业2 该作业序列是一个可行排序，因此作业集合6,2X 可行； 选择作业 3， 则6,2,3X 。 将其按照期限di非减次序排列可得： ID di 6 2 3 3 2 4 3 -101234 作业6 作业3作业2 该作业序列是一个可行排序，因此作业集合6,2,3X 可行； 选择作业 5，则6,2,3,5X 。将其按照期限di非减次序排列可 得： ID di 5 1 6 2 3 3 2 4 -101234 作业6 作业3作业2 作业5 该作业序列是一个可行排序，因此作业集合6,2,3,5X 可行； 选择作业 1， 则6,2,3,5,1X 。 将其按照期限di非减次序排列可 得： ID di 5 1 6 2 3 3 1 3 2 4 -101234 作业6 作业3作业2 作业5 作业1（冲突） 该集合无可行排序，因此6,2,3,5,1X 不可行，6,2,3,5X ； 4 选择作业 0，则6,2,3,5,0X 。将其按照期限di非减次序排列 可得： ID di 5 1 0 1 6 2 3 3 2 4 -101234 作业6 作业3作业2 作业5 作业0（冲突） 该集合无可行排序， 因此6,2,3,5,0X 不可行，6,2,3,5X ； 选择作业 4，则6,2,3,5,4X 。将其按照期限di非减次序排列 可得： ID di 5 1 6 2 4 2 3 3 2 4 该集合无可行排序， 因此6,2,3,5,4X 不可行，6,2,3,5X ； 综 上 所 述 ， 作 业 集 合2,3,6,5X 为 最 优 解 。 且 此 时 收 益 为 3020 18674。 6-8 设3,7,8,9,15,16,18,20,23,25,28W ，请按照上述准则，构造一课最优 3 路 合并树。 解析：11n ，3k 。1 %110%20nk，因此不用补充虚结点（可 参考105P） ； 上述准则为：若n是非负整数，且满足mod11nk ，则使用构造二路 合并最佳模式树的最优解亮度标准(带权外路径长度最小)，将对所有 5 011 , n Ww ww 生成一棵最优k路合并树。 按照上述准则，构造出的一棵3路合并树如下图所示： 172 56 18 7640 182091516232528 378 6-9 图,GV E是一个无向连通图，nV，mE。且 1.99 mO n。试问选 择何种算法求图的最小代价生成树，是Prim算法还是Kruskal算法？ 解析：已知Prim算法时间复杂度为 2 O n，受顶点n影响； Kruskal算法时间复杂度为O m logm，受边数m影响； 因为 1.99 mO n，说明G的边数较顶点数更多，因此选用Prim算法更为合适。 6-12 设有13个程序需存放在 3 条磁带 0 T、 1 T和 3 T上，程序长度分别为 12,5,8,32,7,5,18,26,4,3,11,10,6。请给出最优存储方案。 解析：首先将这 13 个程序按照程序长度非降序排列，得： 程序ID 9 8 1 5 12 4 2 11 10 0 6 7 3 程序长度ai 3 4 5 5 6 7 8 10 11 12 18 26 32 根据定理可知，按照程序编号存放方案如下： 磁带编号 程序ID T0