算法设计与应用 试卷1答案

《算法设计与分析》试题答案A卷 第2页共5页试卷1答案选择题（共15小题，每小题3分，共45分）C.C.B.A.D.B.C.D.B.D.C.B.D.B.二、简答计算题(共4小题，共30分)1.有数组A=⟨29,18,10,15,20,9,5,13,2,4,15⟩，问1：这是最大堆吗？如果不是请交换两个数据，使之成为堆，问2：将根元素删除后，写出使数组重新成为一个堆的步骤（即写出数组的每一次交换）(6)答：1）此数组不是堆，将18和20交换后成为堆（2分）2）A=⟨15,20,10,15,18,9,5,13,2,4⟩A=⟨20,15,10,15,18,9,5,13,2,4⟩A=⟨20,18,10,15,15,9,5,13,2,4⟩（注：可以用树表示）（4分）2.使用动态规划求解0-1背包问题：如有编号分别为1，2，3，4的4件物品，它们的重量分别是2,3,4,5，它们的价值分别是3,4,5，6，现在给你个承重为8的背包，如何让背包里装入的物品具有最大的价值总和?1）写出自底向上的计算m值（最大价值）的矩阵，得出最大价值总和（5分）2）根据m值矩阵得出最优装物品的方案（简要说明如何得到最优装物品方案）（3分）参考答案：1）m值矩阵为（5分）最大价值为10.2）m[4,8]=10是由m[3,3]=4加上第4个物品的价值6得到，所有，最优方案包含物品4m[3,3]=4来自于m[2,3]=4，所以最优方案不包含物品3m[2,3]=4是由m[1,0]=0加上第2个物品的价值4得到，所有，最优方案包含物品2可得，最优方案包含物品2和物品4.（3分）3.钱币兑换问题：有一个货币系统，它有n中硬币，面值分别为v1=1,v2=2，vn=5.我们需要兑换价值为17的钱币，要让硬币的数目最少。请用动态规划求解此问题。要求：1）列出递归式；2）自底向上的计算1到17的每个M值（最少硬币数目）,需要指出每个M是由之前的哪个M值得出的。（6）答（注：以下为参考答案，可定义其他递归式）：1）（2）2)M0=0,M1=1（M0+1）,M2=1（M0+1）,M3=2（M1+1）,M4=2（M2+1）,M5=1（M0+1）,M6=2（M5+1）,M7=2（M5+1）,M8=3（M7+1）,M9=3（M7+1）,M10=2（M5+1）,M11=3（M10+1）M12=3（M10+1）,M13=4（M12+1）,M14=4（M12+1）,M15=3（M10+1）,M16=4（M15+1）,M17=4（M15+1）最优方案为：2+5+5+5（4分）4.用分支限界法解决如下图所示的旅行商问题。要求：1）给出边界（上界和下界）；2）画出搜索树，对树中的每个节点给出编号（访问顺序）、下界、以及节点是否舍弃（按照上界条件）。（10分）参考答案1:下界为：所有节点的最短两条边只和除以2,初始下界为（5+6+6+7+5）/2=14（向下取整）；上界为：按照贪心算法得出的回路，即从节点a出发依次选择一条最小的边来连接还没有被访问过的节点，直到回到节点a，上界为（2+5+2+3+3）=15（5分）（5分）参考答案2:下界为：所有节点的最短两条边只和除以2,初始下界为（5+6+6+7+5）/2=15（向上取整）；上界为：按照贪心算法得出的回路，即从节点a出发依次选择一条最小的边来连接还没有被访问过的节点，直到回到节点a，上界为（2+5+2+3+3）=15，所以可以直接得出最优解为15（5分）搜索树，可参考上述搜索树（5分）三、综合分析题(2小题，共25分)给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。如区间集合[[1,2],[2,3],[3,4],[1,3]]，移除[1,3]即可使得剩余区间不重叠（[1,2]和[2,3]不重叠）。要求：1.设计一个贪心算法解决以上问题，2.并说明算法的计算复杂度（区间个数为n），3.说明算法是最优算法，并证明之。（12分）答（仅做参考，可通过其他算法实现，只要算法正确，都给分）：按照区间的结尾进行排序，每次选择结尾最小的，且和前一个区间不重叠的区间，剩余的区间即被移除的区间（此问题等同于时间安排问题）（4分）nlogn（排序的复杂度）（2分）是最优算法。（6分）证明：设（a1，a2,a3，…,am）为本算法选出的解，（b1，b2,b3，…,bm）为最优解。下面证明b1可以用a1替换，因为a1的结束时间早于b1，则b1可用a1替换任保持最优解，所以（a1，b2,b3，…,bm）为最优解，依次类推，逐步用（a1，a2,a3，…,am）替换（b1，b2,b3，…,bm）任保持最优解，所以（a1，a2,a3，…,am）是最优解。子集和问题：给出某个集合W={w1,w2…wi…wn-1,wn}和M值，请找出W的子集其和为M。如n＝4,W=(wl，w2，w3，w4)＝(11，13，24，7)，M＝31，则子集(11，13，7)和子集(24，7)的和为M.如果用1代表入选的元素，0代表没入选的元素，则上述例子的答案为（1，1，0，1）and（0，0，1，1），最优解为元素最少的解。请用回溯法求解子集和问题：描述回溯法的解空间和树结构，并简单画出此树（3分）说明你的剪枝函数（边界函数和约束函数）（4分）给出找到最优解的非递归伪代码（需要考虑边界函数和约束函数）（6分）参考答案：解空间有每个元素的取与不取组成，则总共有2n个可行解。其组成的树结构为此树中，左子树表示取相应的元素，右子树表示不取约束函数为已经加入元素的总和不能超过M（左子树），边界函数为即使将剩余元素全部加入也小于M（右子树）（仅做参考，可设计其他约束函数，只要正确都给分）。（代码只要逻辑正确就可得分）BACKTRACKING()//k=1,X=2//初始化OP_Num=inf//记录最优值（元素个数）Num=0，WT=0//当前值元素个数，和当前总和whilek>0 X[k]=X[k]-1;IfX[k]==0//从1跳到0，需要将重量减去WT=WT-w(k);Num=Num-1;IfWT+剩余节点总和<=M//无须再往下遍历，回溯X[k]=2; k=k-1;continueifX[k]==1 ifWT+w(k)<=MWT=WT+w(k);Num=Num+1;ElseX[k]=0; ifX[k]>=0//k是否已经遍历完毕ifk==n ifWT==M并且Num<OP_NumOP_Num=Num；//更新最优值X[k]=2;k=k-1else