计算机与信息科学学院2010-2011学年第2学期模拟试卷计算机算法设计与分析—第四章.贪心算法本卷满分100分 完卷时间120分钟一. 简答题（每小题2分，共20分）1. 当一个问题具有 且具有 时可用贪心算法，如最小生成树问题（背包问题，活动安排问题等）。

2. 在动态规划可行的基础上满足 才能用贪心。

3. 贪心算法总是作出在当前看来最好的选择。

也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的 选择。

4. 动态规划算法通常以 的方式解各子问题，而贪心算法则通常 以 的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题5. 贪心算法和动态规划算法都要求问题具有 性质，这是2类算法的一个共同点。

6. 当一个问题的最优解包含其子问题的最优解时，称此问题具有 。

7. 对于具有n 个顶点和e 条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra 算法的主循环体需要时间。

这个循环需要执行n-1次，所以完成循环需要 时间。

算法的其余部分所需要时间不超过 。

8. 0-1背包问题指：给定n 种物品和一个背包。

物品i 的重量是Wi ，其价值为Vi ，背包的容量为C 。

应如何选择装入背包的物品，使得装入背包中物品的 最大。

9. 有一批集装箱要装上一艘载重量为c 的轮船。

其中集装箱i 的重量为Wi 。

最优装载问题要求确定在 不受限制的情况下，将 装上轮船。

10. 多机调度问题要求给出一种作业调度方案，使所给的n 个作业在 由m 台机器加工处理完成。

二. 综合题（1-6题每题7分，7-8题每题9分，共60分）1. 有4个物品，其重量分别为(4, 7, 5, 3)，物品的价值分别为(40, 42, 25,12)，背包容量为10。

试设计3种贪心策略,并给出在每种贪心策略下背包问题的解。

)(n O2. 使用prim算法构造出如下图G的一棵最小生成树。

dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=63. 设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。

作业i所需要的处理时间为ti。

约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。

多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。

设计算法，并讨论是否可获最优解。

4. 设有n种面值为:d1≥d2≥……≥dn的钱币，需要找零钱M，如何选择钱币dk ，的数目Xk，满足 d1×Xi＋……dn×XnM ，使得Xi＋ (X)n最小。

请选择贪心策略，并设计贪心算法。

5. 在下列空格中填入适当的语句完成贪心方法的抽象化控制procedure GREEDY(A，n)//A(1：n)包含n个输入//solutions←①；for i←1 to ② dox←SELECT(A)if FEASIBLE(solution，x)then solutions←③；endif④；return(solution)end GREEDY6. 填空完成背包问题的贪心算法procedure GREEDY-KNAPSACK(P，W，M，X，n)X←0 //将解向量初始化为零//cu←M //cu是背包剩余容量//for i←1 to n doif ① then exit endifX(i) ←②；cu←③；④；if i≤n then X(i) ←⑤；endifend GREEDY-KNAPSACK7. 填空完成带有限期的作业排序line procedure JS(D，J，n，k)//D(1)，…，D(n)是期限值。

n≥1。

作业已按p1≥p2≥…pa被排序。

J(i)是最优解中的第i个作业，1≤i≤k。

终止时，D(J(i)≤D(J(I+1))，1≤i<k//1 integer D(0：n)，J(0：n)，i，k，n，r2 D(0)←J(0) ←0 //初始化//3 k←1；J(1) ←1 //计入作业1//4 for ① to n do5 ② ;6 while ③ and ④ do7 ⑤ ;8 repeat9 if D(J(r))≤D(i) and D(i)>r then10 for ⑥⑦ by-l do11 ⑧；12 repeat13 ⑨；k←k+1；14 endif15 repeat16 end JS8. 有n 个活动争用一个活动室。

已知活动i占用的时间区域为[si ，fi]，活动i,j相容的条件是：sj≥fi ，问题的解表示为(xi| xi=1，2…，n,)，xi表示顺序为i的活动编号活动，求一个相容的活动子集，且安排的活动数目最多。

三.简答题（每题5分，共20分）1.简述贪心法的设计思想。

2.简述Kruskal算法构造G的最小生成树的基本思想3.试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。

4.简述贪心算法与动态规划算法的差异参考答案：一、 填空题：1.最优子结构性质 贪心选择性质2.贪心选择性3.局部最优4.自底向上 自顶向下5.最优子结构6.最优子结构性质7.O （n2） O （n2）8.总价值9.尽可能多的集装箱 10.尽可能短的时间内二、综合题：1. 解：重量最轻：装入1，4，3.总价值：40+12+25*3/5=67 价值最大：装入1，2。

总价值：４０*3/4+42=72 性价比最小：装入1，2.总价值：40+6/7*42=76 2.解：3.解：对于处理机j ，用S[j] 表示处理机j 已有的作业数，用P[j,k]表示处理机j 的第k 个作业的序号 。

1）将作业按照t[1]≥t[2]≥……≥t[n]排序2）S[1:m]清零 j ←0 //从第一个处理机开始安排 3) for i ←1 to n do //安排n 个作业 j ←j mod m +1 //选下一个处理机 S[j]←S[j]+1; P[j,S[j]]←i ；Repeat4.解：贪心原则：每次选择最大面值硬币。

CU←M;i←1;X←0 // X为解向量While CU≠0 doX[i]←CU div d[i] // X[i]为第i中硬币数CU←CU-d[i]*X[i←i+1;repeat5.①Φ② n ③ UNION(solution，x) ④ repeat6. ① W(i) ≤ cu ② 1 ③cu-W(i) ④repeat ⑤cu/ W(i)7. ① i=2 ②r ← k ③D(J(r))>D(i) ④D(J(r))<>r⑤r←r-1 ⑥ l←k ⑦ r+1 ⑧ J(I+1) ←J(l) ⑨ J(r+1)←i8. 解：解决这个问题的基本思路是在安排时应该将结束时间早的活动尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。

据此，贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。

在贪心算法中，将各项活动的开始时间和结束时间分别用两个数组s和f存储，并使得数组中元素的顺序按结束时间非减排列：f1? f2?…? fn。

算法如下：GreedyAction(s, f，n) // s[1:n]、f[1:n]分别代表n项活动的起始//时间和结束时间, 并且满足f[1]? f[2]?…? f[n]j=1; solution={1}; //解向量初始化为空集for i ←2 to n doif si?fj thensolution=solution ? {j}; // 将j加入解中j=i;endifendforreturn(solution);end Greedy三.简答题1.把一个问题分解为一系列较为简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解。

（指根据当前已有信息做出选择，不从整体最优考虑，只选择局部最优）2.首先将G的n个顶点看成n个孤立的连通分支。

将所有的边按权从小到大排序。

然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。

这个过程一直进行到只剩下一个连通分支时为止。

3.贪心算有效性：最小生成树、哈弗曼、活动安排、单元最短路径。

无效反例：0——1背包问题，无向图找最短路径问题。

4.贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。

但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。