判断题能够用贪心算法求解的问题一定能用动态规划求解 --------F
贪心算法需要满足两个条件，贪心选择性和最优子结构，动态规划算法需要满足最优子结构和重复子问题，满足贪心算法两要素的问题不一定满足动态规划算法的两个要素。 问题一设有n个正整数，将它们连接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。
又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。
输入是n个正整数，输出是这n个正整数连成的最大多位整数，要求用贪心法求解该问题。答案要求包含以下内容：（1）证明问题具有贪心选择性；（2）证明问题具有优化子结构；（3）写出算法伪代码并分析算法的时间复杂度。
贪心选择性：每次选择最高位最大的数字优先输出，如果最高位相同则比较次高位，同样选择数字较大的，如果是类似123，,1230这样的情况，选择位数较少的数字。
以最高位不同为例进行证明：
假设a1a2...aib1b1...bn−ia_1a_2...a_ib_1b_1...b_{n-i}a1a2...aib1b1...bn−i是最大多位数，且其最高位所在的数字a1a2...aia_1a_2...a_ia1a2...ai不是依据上述贪心思想选择出来的，则一定有数字c1c2...cjc_1c_2...c_jc1c2...cj满足c1>a1c_1>a_1c1>a1，下面证明以c1c2...cjc_1c_2...c_jc1c2...cj开头的数字c1c2...cjd1d2...dn−jc_1c_2...c_jd_1d_2...d_{n -j}c1c2...cjd1d2...dn−j比a1a2...aib1b1...bn−ia_1a_2...a_ib_1b_1...b_{n-i}a1a2...aib1b1...bn−i大。
a1a2...aib1b1...bn−i<（a1+1）∗10n−1a_1a_2...a_ib_1b_1...b_{n-i}<（a_1+ 1）*10^{n-1}a1a2...aib1b1...bn−i<（a1+1）∗10n−1
c1c2...cjd1d2...dn−j≥c1∗10n−1c_1c_2...c_jd_1d_2...d_{n -j}\geq c_1*10^{n-1}c1c2...cjd1d2...dn−j≥c1∗10n−1
因为c1>a1c_1>a_1c1>a1所以c1∗10n−1≥(a1+1)∗10n−1c_1*10^{n-1}\geq (a_1+1)*10^{n-1}c1∗10n−1≥(a1+1)∗10n−1,进而得到c1c2...cjd1d2...dn−jc_1c_2...c_jd_1d_2...d_{n -j}c1c2...cjd1d2...dn−j比a1a2...aib1b1...bn−ia_1a_2...a_ib_1b_1...b_{n-i}a1a2...aib1b1...bn−i大，与 a1a2...aib1b1...bn−ia_1a_2...a_ib_1b_1...b_{n-i}a1a2...aib1b1...bn−i是最大的多位数矛盾。
最优子结构：复制-黏贴法容易证明。 bool campare(string i, string j){
return (i+j) > (j+i);}sort(tmp.begin(), tmp.end(), campare); // campare为假时交换i 和 j
平均时间复杂度O(nlgn)O(nlgn)O(nlgn) 问题二存放于磁带上文件需要顺序访问。故假设磁带上依次存储了n个长度分别是L[1],….,L[n]的文件，则访问第k个文件需要顺次访问前K个文件（老师题目缺失） 。现给定n个文件的长度L[1],….,L[n]，并假设每个文件被访问的概率相等，试设计一个算法输出这n个文件在磁带上的存储顺序使得平均访问代价最小。
答案要求包含以下内容：（1）证明问题具有贪心选择性；（2）证明问题具有优化子结构；（3）给出算法并分析算法的时间复杂度。
存储方式：长度最短的存在最前面。 平均访问长度为∑i=1np∗Li=p∗(n∗L1+(n−1)∗L2+...+Ln)\sum_{i = 1}^np*L_i=p*(n * L_1 + (n-1)*L_2+...+L_n)∑i=1np∗Li=p∗(n∗L1+(n−1)∗L2+...+Ln),p=1/np=1/np=1/n 证明贪心选择性：利用上述的平均访问长度表达式即可证明。 最优子结构：略。 将长度排序即可。平均时间复杂度是O(nlgn）O(nlgn）O(nlgn）
题目三G=(V, E)是一个具有n个顶点m条边的连通图，且可以假设边的代价为正且各不相同，设，定义T的瓶颈边是T中代价最大的边，G的一个生成树T是一棵最小瓶颈生成树，如果不存在G的生成树T’使得它具有代价更小的瓶颈边。
问:(1)G的每棵最小瓶颈树一定是G的一棵生成树吗？证明或者给出反例;
(2) G的每棵生成树都是G的最小瓶颈树吗？证明或者给出反例。 是。由最小瓶颈树的定义可知G的最小瓶颈树是G的生成树。 是。证明：l1<l2<l3...<lml1<l2<l3...<lml1<l2<l3...<lm,这m个数是G中m条边的权值。最小生成树中的边是l1,l2,l3...ln−1l1,l2,l3...l{n-1}l1,l2,l3...ln−1，G的最小瓶颈树中有(n-1)条边,显然在G中无法找到（n-1）条边，并且这些边中最大的权值小于ln−1ln-1ln−1。
题目四给定n个自然数d1, d2, …, dn, 设计算法，在多项式时间确定是否存在一个无向图G，使它的结点度数准确地就是d1, d2, …, dn， 要求G中在任意两个结点之间至多有一条边，且不存在一个结点到自身的边。 d\\数组，保存规定的各点的度
sort（d）//将d数组按照数值从大到小排序for i = 1 to n
end = d[i]
for j = (i + 1) to min(n, i + end)
if d[j] > 0 && d[i] > 0
d[j]--
d[i]--
if d[i] == 0
break
if d[i] > 0
return false//表示不可以生成指定权值的图return true
时间复杂度O(nlgn)O(nlgn)O(nlgn) 题目五在一个操场上摆放着n堆石子，现要将石子有次序地合并成一堆。规定每次只能选择任意两堆石子合并成新的一堆，并将新一堆石子数记为该次合并的得分。试设计贪心算法，计算出将n堆石子合并成一堆的最小得分和最大得分，写出算法的伪代码并分析算法的计算复杂性。（数组d记录这n堆石子的石子数，下标范围是0-(n-1)）
计算合并这n堆石子的最小得分，最大得分类似。（sum记录合并这个石子堆的代价）
以计算最小得分为例： 初始化sum为0 将数组d按照从小到大的顺序排序 取出最小的两个石子堆d[i],d[j],将d[i],d[j]从数组中删除，将d[i]+d[j]加进d数组，sum加上d[i]+d[j], 如果数组d大小是1，则返回sum，否则继续第2步
使用堆排序。
题目六利用贪心法设计算法求解下述问题：
输入：正整数集合S，正整数W
输出：S的子集合S’，其中元素之和不小于W，且S’是满足这个条件的子集合中包含元素数量最少的。
要求：(1) 阐明贪心思想 (2) 写出伪代码 (3) 证明算法正确性 (4) 分析算法时间复杂度 按照从大到小的顺序挑选S中的正整数。
S //表示正整数集合S'表示即将输出的S的子集合sort(S)//表示将集合中的元素排序，排序之后假设按照从大到小的顺序排序sum = 0while sum < W
max = getMax(S)//表示得到S中最大的正整数
delete(S, max)//表示将S中的数值是max的数字删去一个
add(S', max)//表示将max加进S'集合
sum += maxreturn S'
证明贪心选择性和最优子结构即可。
贪心选择性：最优解中一定包含S中现有正整数的最大值。
假设S={s1,s2,s3...sn}S=\{s_1,s_2,s_3...s_n\}S={s1,s2,s3...sn}且满足s1≤s2≤s3...≤sns_1\leq s_2\leq s_3...\leq s_ns1≤s2≤s3...≤sn,则最优解S’中一定要包含sns_nsn.
如果S′={a1,a2,a3,...an},a1≤a2≤...≤anS'=\{a_1,a_2,a_3,...a_n\},a1\leq a2\leq ...\leq a_nS′={a1,a2,a3,...an},a1≤a2≤...≤an是最优解。且∑1nai=sum1≥W\sum_1^nai = sum_1\geq W∑1nai=sum1≥W,现在使用sns_nsn替换a1a_1a1得到新的集合Snew={a2,a3,...an,sn}S_{new}=\{a_2,a_3,...a_n,s_n\}Snew={a2,a3,...an,sn}，则∑2nai+sn≥sum1\sum_2^nai+s_n\geq sum_1∑2nai+sn≥sum1,即S’‘可以作为最优解甚至删除S’'中的a2a_2a2之后，仍然是满足要求的,综上，最优解中一定包含S中最大的正整数。
最优子结构：略。 时间复杂度：排序的平均时间复杂度是O(nlgn)O(nlgn)O(nlgn)的，下面的循环是O(n)O(n)O(n)的，所以算法整体是O(nlgn)O(nlgn)O(nlgn)的。
题目七现有一块草坪，长为m米，宽为n米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri的圆被湿润，设有充足的喷水装置，并且一定能把草坪全部湿润，设计算法选择尽量少的喷水装置，把整个草坪的全部湿润。要求写出伪代码并分析算法正确性和复杂性。
喷水装置的喷灌范围是圆形，如上图所示，最靠左的装置一定可以喷灌到矩形的左上角，第一个装置形成的圆形记为S1，第二是S2，则S1和S2的交点一定在矩形的边界线上。
策略是选择喷灌范围最大的喷灌装置，直到选择的装置可以喷灌整个矩形草坪。假设R1≥R2≥R3...≥RnR_1\geq R_2\geq R_3...\geq RnR1≥R2≥R3...≥Rn
最优解是选择R1≥R2≥R3...≥RmR_1\geq R_2\geq R_3...\geq R_mR1≥R2≥R3...≥Rm
使得∑i=1mRi2−n2/4≥m\sum_{i=1}^m\sqrt{R_i^2-n^2/4}\geq m∑i=1mRi2−n2/4≥m且∑i=1m−1Ri2−n2/4<m\sum_{i=1}^{m-1}\sqrt{R_i^2-n^2/4}< m∑i=1m−1Ri2−n2/4<m
算法正确性的证明，利用上面这个式子，就可以很简单的说明贪心选择性，最优子结构还是一样的套路。
时间复杂度O(nlgn)O(nlgn)O(nlgn) 题目八设计贪心算法求解如下的最大生成树问题。
输入：无向连通图G=(V,E)，非负加权函数w:ER+;
输出：各边权值之和达到最大值的生成树T=(V,E’)
1.简述算法的贪心思想；
2.叙述并证明问题的贪心选择性；
3.叙述问题的优化子结构
4.用伪代码表述算法并分析其时间复杂度 题目九在黑板上写了n个正数组成的一个数列，进行如下操作：每一次擦去其中两个数a和b, 然后在数列中加入一个数a*b+1，如此下去黑板上只剩下一个数。在所有按这种方法最后得到的树中，最大的数记为max，最小的数记为min，则该数列的极差M定义为M=max-min。对于给定数列，设计贪心算法计算出其极差M，要求分析算法的正确性，写出算法的伪代码并分析其复杂性。 题目十哈工大的机器人研究团队现有不同类型的登山机器人，这些登山机器人可以携带有限的能量登山。在登山过程中，登山机器人需要消耗一定能量，连续攀登的路程越长，其攀登的速度就越慢。在对m种不同类型的机器人进行性能测试时，已测定出机器人i连续攀登1，2，…，n米所用的时间分别为ti1, ti2, …, tin。现在要对这m个机器人进行综合性能测试，举行机器人接力连续攀登演习。攀登的总高度为s米。规定每个机器人攀登1次，每次至少攀登1米，最多攀登n米，而且每个机器人攀登的高度必须是整数，即只能在整米处接力。安排每个机器人攀登适当的高度，使完成接力攀登的总时间最短，完成下列问题。
例子：若有3个机器人，每个机器人连续攀登1,2,3米所用的时间如表中所示。每个机器人最多可以攀登3米，攀登的总高度为5米，则使完成接力攀登的总时间最短的安排方案为1号机器人攀登2米，2号机器人攀登2米，3号机器人攀登1米。 （1）证明该问题具有贪心选择性；
（2）证明该问题具有优化子结构；
（3）根据该贪心选择性和优化子结构用伪代码写出算法；
（4）分析算法的时间复杂度。
|
