第四章-贪心算法(模拟试题)

计算机与信息科学学院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 O

2. 使用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)=6

3. 设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i

所需要的处理时间为t

i

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

多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。

4. 设有n种面值为:d

1≥d

2

≥……≥d

n

的钱币，需要找零钱M，如何选择钱

币d

k ，的数目X

k

，满足 d

1

×X

i

＋……d

n

×X

n

M ，使得X

i

＋……X

n

最小。

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

5. 在下列空格中填入适当的语句完成贪心方法的抽象化控制

procedure GREEDY(A，n)

//A(1：n)包含n个输入//

solutions←①；

for i←1 to ② do

x←SELECT(A)

if FEASIBLE(solution，x)

then solutions←③；

endif

④；

return(solution)

end GREEDY

6. 填空完成背包问题的贪心算法

procedure GREEDY-KNAPSACK(P，W，M，X，n)

X←0 //将解向量初始化为零//

cu←M //cu是背包剩余容量//

for i←1 to n do

if ① then exit endif

X(i) ←②；

cu←③；

④；

if i≤n then X(i) ←⑤；

endif

end GREEDY-KNAPSACK

7. 填空完成带有限期的作业排序

line procedure JS(D，J，n，k)

//D(1)，…，D(n)是期限值。n≥1。作业已按p

1≥p

2

≥…p

a

被排序。J(i)

是最优解中的第i个作业，1≤i≤k。终止时，D(J(i)≤D(J(I+1))，1≤i

1 integer D(0：n)，J(0：n)，i，k，n，r

2 D(0)←J(0) ←0 //初始化//

3 k←1；J(1) ←1 //计入作业1//

4 for ① to n do

5 ② ;

6 while ③ and ④ do

7 ⑤ ;

8 repeat

9 if D(J(r))≤D(i) and D(i)>r then

10 for ⑥⑦ by-l do

11 ⑧；

12 repeat

13 ⑨；k←k+1；

14 endif

15 repeat

16 end JS

8. 有n 个活动争用一个活动室。已知活动i占用的时间区域为[s

i ，f

i

]，活动

i,j相容的条件是：sj≥f

i ，问题的解表示为(x

i

| x

i

=1，2…，n,)，x

i

表示

顺序为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 ；

Repeat

4.解：

贪心原则：每次选择最大面值硬币。

CU←M;i←1;X←0 // X为解向量

While CU≠0 do

X[i]←CU div d[i] // X[i]为第i中硬币数

CU←CU-d[i]*X[

i←i+1;

repeat

5.①Φ② n ③ UNION(solution，x) ④ repeat

6. ① 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)←i

8. 解：解决这个问题的基本思路是在安排时应该将结束时间早的活动尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。据此，贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。在贪心算法中，将各项活动的开始时间和结束时间分别用两个数组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 do

if si?fj then

solution=solution ? {j}; // 将j加入解中

j=i;

endif

endfor

return(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个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。

第四章-贪心算法(模拟试题)

计算机与信息科学学院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 O

第四章贪心算法

第四章贪心算法 一、课本+作业 DIJKSTRA的主要思想 算法的思想是把中心定在起始顶点，向外层结点扩展，最终在目标顶点结束，停止扩展。设顶点集合为S，通过贪心选择，逐步扩充这个集合。一开始，集合S中所包含顶点仅为源点。设u为图G的某一结点，把从开始顶点到结点u，且中间经过的顶点均在集合S内的线路称为从源点到u的特殊路径。 创建一个数组SD，用于储存每个顶点所对应的最短特殊路径的长度。算法每次从u∈V-S 中取出具有最短特殊路长度的顶点u，将u添加到集合S中，与此同时，修改数组SD。当S包含了所有V中顶点时，SD就记录了从源到所有其它顶点之间的最短路径长度。 Dijkstra算法的时间复杂度为O(n2)，空间复杂度随着选择的存储方式不同而有所变化，若存储方式为邻接矩阵时为O(n2)。在求解单源最短路径问题时，Dijkstra算法可以得到最优解，但由于它需要遍历众多结点，所以效率低。

历年试题 1.（2011年）试用Prim算法求解下面无向赋权图的最小生成树，指出最小生成树及该树中各边被选中的先后次序；写出算法的基本步骤。

2. (2010)1.分析Kruskal 算法的时间复杂度； 2. 试用下面的例子说明用Kruskal 算法求解最优生成树问题，并总结出算法的 基本步骤： 3.(2009)（原理习题有） 4. (2006) 设n p p p ,,,21 是准备存放到长为L 的磁带上的n 个程序，程序i p 需要的带 长为i a 。设L a n i i >∑=1，要求选取一个能放在带上的程序的最大子集合（即其中含有 最多个数的程序）Q 。构造Q 的一种贪心策略是按i a 的非降次序将程序计入集合。 1). 证明这一策略总能找到最大子集Q ，使得∑∈≤Q p i i L a 。

算法分析习题参考答案第四章

第四章作业 部分参考答案 1． 设有n 个顾客同时等待一项服务。顾客i 需要的服务时间为n i t i ≤≤1,。应该如何安排n 个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由（证明）。 策略： 对 1i t i n ≤≤进行排序，,21n i i i t t t ≤≤≤ 然后按照递增顺序依次服务12,,...,n i i i 即可。 解析：设得到服务的顾客的顺序为12,,...,n j j j ，则总等待时间为 ,2)1(121n n j j j j t t t n nt T +++-+=- 则在总等待时间T 中1j t 的权重最大，jn t 的权重最小。故让所需时间少的顾客先得到服务可以减少总等待时间。 证明：设,21n i i i t t t ≤≤≤ ，下证明当按照不减顺序依次服务时，为最优策略。 记按照n i i i 21次序服务时，等待时间为T ，下证明任意互换两者的次序，T 都不减。即假设互换j i ,)(j i <两位顾客的次序，互换后等待总时间为T ~ ，则有 .~ T T ≥ 由于 , ))(())(()2)(2()1)(1(21n j i i i i i i t j t j n i t i n t n t n T +--++--++--+--=,))(())(()2)(2()1)(1(~ 21n i j i i i i i t j t j n i t i n t n t n T +--++--++--+--= 则有 .0))((~ ≥--=-i j i i t t i j T T 同理可证其它次序，都可以由n i i i 21经过有限次两两调换顺序后得到，而每次交换，总时间不减，从而n i i i 21为最优策略。 2． 字符h a ~出现的频率分布恰好是前8个Fibonacci 数，它们的Huffman 编码是什么？将结果推广到n 个字符的频率分布恰好是前n 个Fibonacci 数的情形。Fibonacci 数的定义为：1,1,11210>+===--n if F F F F F n n n

ch4_贪心算法

78 第四章 贪心算法 §1.贪心算法基本思想 找零钱 假如售货员需要找给小孩67美分的零钱。现在，售货员手中只有25美分、10美分、5美分和1美分的硬币。在小孩的催促下，售货员想尽快将钱找给小孩。她的做法是：先找不大于67美分的最大硬币25美分硬币，再找不大于67－25＝42美分的最大硬币25美分硬币，再找不大于42－25＝17美分的最大硬币10美分硬币，再找不大于17－10＝7美分的最大硬币5美分硬币，最后售货员再找出两个1美分的硬币。至此，售货员共找给小孩6枚硬币。售货员的原则是拿尽可能少的硬币个数找给小孩。 从另一个角度看，如果售货员将捡出的硬币逐一放在手中，最后一起交给小孩，那么售货员想使自己手中的钱数增加的尽量快些，所以每一次都尽可能地捡面额大的硬币。 装载问题 有一艘大船用来装载货物。假设有n 个货箱，它们的体积相同，重量分别是，货船的最大载重量是c。目标是在船上装更多个数的货箱该怎样装？当然，最简单的作法是“捡重量轻的箱子先往上装”，这是一种贪心的想法。如果用表示装第个货箱，而n w w w ,,21"1=i x i 0=i x 表示不装第i 个货箱，则上述问题是解优化问题： 求，使得 n x x x ,,,21" (4.1.1) ∑=n i i x 1max 满足条件 (4.1.2) 1 w ,0n i i i i x c x =≤=∑,1贪心算法，顾名思义，是在决策中总是作出在当前看来是最好的选择。例如找零钱问题中，售货员每捡一个硬币都想着使自己手中的钱尽快达到需要找钱的总数。在装载问题中，每装一个货箱都想着在不超重的前提下让船装更多的箱子。但是贪心方法并未考虑整体最优解，它所作出的选择只是在某种意义上的局部最优选择。当然，在采用贪心算法时未必不希望结果是整体最优的。事实上，有相当一部分问题，采用贪心算法能够达到整体最优，如前面的找零钱问题以及后面将要讲到的单点源最短路径问题、最小生成树问题、工件排序问题等。为了更好理解贪心算法，我们将装载问题稍加推广，考虑可分割的背包问题。 背包问题 已知容量为M 的背包和件物品。第i 件物品的重量为，价值 n i w

第四章算法作业

骆吉洲作业： 1. 设有n种不同面值的硬币，个个硬币的面值存于数组T[1:n]中。现在用这些硬币来找钱。各种硬币使用的各数不限。 （1）当只用面值为T[1]、T[2],…,T[i]来找出钱j时，所用的硬币的最小个数记为C(i,j),写出C(i,j)的递推式。 （2）设计一个动态规划算法以计算C(n,j)，1≤j≤L，并且只使用一个规模为L的数组，并分析该算法的复杂度。 （3）设C(n,j)，1≤j≤L已经计算出来，对任意钱数m（小于等于L），确定用最少硬币数找出钱m的策略。证明该问题有贪心选择性，设计解该问题的贪心算法，并分析其复杂度。 答： （1）递推式： C(i,j)={ 0 j=0 j/T[1] j>0且i=1 min 1≤k≤j/T[i] {k+C(i?1,j?k×T[i])} j>0且i≠1 （2）算法设计：根据（1）中的递推公式，计算C(i,j)时只可能会用到C(i-1,x)，其中x的取值区间为[1,j-1]。不会使用x>j的元素数值。假设一个n×L阶矩阵，只需要从左往右计算，每列从上往下计算C(i,j)，并使用一个规模为L的数组即可。 算法伪代码： Input：硬币面值数组T[1:n]，待找钱数L Output：使用硬币的最小个数x的数组 GET-CHANGE(T,L)

1 n←length(T) 2 create array x[1:L] 3 for j←1 to L 4 d o x[j]←j/T[1] 5 for i←2 to n 6 do for j←L to 1 7 do for k←1 to j/T[i] 8 do if x[j-k*x]+k