2021算法分析习题参考答案第五章 (1)

算法分析习题参考答案第五章 (1) - 让每个人平等地提升自我！ 100 1最大子段和问题：给定整数序列 n a a a ,21 ，求该序列形如=ji k k a 的子段和的最大值： =j i k k n j i a 1max ,0max 1) 已知一个简单算法如下：int Maxsum(int n,int a,int& besti,int& bestj)int sum = 0;for (int i=1;iint suma = 0;for (int j=i;jsuma + = aj;if (suma sum)sum = suma;besti = i;bestj = j;return sum;试分析该算法的时间复杂性。2) 试用分治算法解最大子段和问题，并分析算法的时间复杂性。3) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。（提示：令1()max ,1,2,j ki j n k i b j a j n =）解：1）分析按照第一章，列出步数统计表，计算可得)(2n O2）分治算法：将所给的序列a1:n分为两段a 1:n/2、an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大子段和有三种可能：a1:n的最大子段和与a1:n/2的最大子段和相同；a1:n的最大子段和与an/2+1:n的最大子段和相同；a1:n的最大子段和为两部分的字段和组成，即j n j i l n i j a a a a a+=+= 122；- 让每个人平等地提升自我！intMaxSubSum ( int *a, int left , int right)int sum =0;if( left=right)sum = aleft 0? a left:0 ;elseint center = ( left + right) /2;int leftsum =MaxSubSum ( a, left , center) ;int rightsum =MaxSubSum ( a, center +1, right) ;int s_1 =0;int left_sum =0;for ( int i = center ; i = left; i-)left_sum + = a i ;if( left_sum s1)s1 = left_sum;int s2 =0;int right_sum =0;for ( int i = center +1; i right_sum + = a i;if( right_sum s2)s2 = right_sum;sum = s1 + s2;if ( sum sum = leftsum;if ( sum sum = rightsum;return sum;int MaxSum2 (int n)int a；returnMaxSubSum ( a, 1, n) ;该算法所需的计算时间T(n)满足典型的分治算法递归分式T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)101 - 让每个人平等地提升自我！ 102 3）设max )(1=j i k k j i a j b ,则最大子段和为).(max max max max max 11111j b a a n j j i k k j i n j j i k k n j n i = 最大子段和实际就是)(,),2(),1(maxn b b b .要说明最大子段和具有最优子结构性质，只要找到其前后步骤的迭代关系即可。 ,)1(max ,max max ,max max )(1111111j j j j j i k k j i j j i j j i k k j i k k j i a a j b a a a a a a a j b +-=+=+=-=-=若0)1(-j b , j a j b j b +-=)1()(；若0)1(-j b ，j a j b =)(。因此，计算)(j b 的动态规划的公式为：.1,)1(max )(n j a a j b j b j j +-=intMaxSum (int* a ，int n )int sum = 0, b = 0，j=0;for( int i=1;iif( b 0) b = b + a i;else b = a i;endif if( b sum) sum = b;j=i ；endifreturn sum;自行推导，答案：时间复杂度为O （n ）。2.动态规划算法的时间复杂度为O （n ）（双机调度问题）用两台处理机A 和B 处理n 个作业。设第i 个作业交给机器A 处理时所需要的时间是i a ，若由机 - 让每个人平等地提升自我！ 103 器B 来处理，则所需要的时间是i b 。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这n 个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：解：（思路一）删除（思路二）在完成前k 个作业时，设机器A 工作了x 时间，则机器B 最小的工作时间是x 的一个函数。设Fkx表示完成前k 个作业时，机器B 最小的工作时间，则其中k b x k F +-)(1对应第k 个作业由机器B 来处理（完成k-1个作业时机器A 工作时间仍是x ，则B 在k-1阶段用时为)(1x k F -）；而)(1k a x k F -对应第k 个作业由机器A 处理（完成k-1个作业，机器A 工作时间是x-ak，而B 完成k 阶段与完成k-1阶段用时相同为)(1k a x k F -）。则完成前k 个作业所需的时间为)(,maxx k F x1）当处理第一个作业时，a1=2,b1=3;机器A 所花费时间的所有可能值范围：0 x a0.x0xx 2时，F1x=0，则Max(2,0)=2；2）处理第二个作业时：x 的取值范围是：0 当x（思路三）假定n 个作业的集合为n S n ,2,1 =。设J 为n S 的子集，若安排J 中的作业在机器A 上处理，其余作业在机器B 上处理，此时所用时间为 =J S j j Jj j b a J T ,max )(，则双机处理作业问题相当于确定n S 的子集J ，使得安排是最省时的。即转化为求J 使得)(min J T nS J 。若记1,2,11-=-n S n ，则有如下递推关系： + += J S j j n J j j S J J S j j J j j n S J I S j j I j j S I b b a b a a b a n n n ,max min ,max min min ,max min 11- 让每个人平等地提升自我！104 （思路四）此问题等价于求（x1,x n），使得它是下面的问题最优解。min maxx1a1+x n a n，(1-x1)b1+(1-x n)b n x i=0或1，i=1n基于动态规划算法的思想，对每个任务i，依次计算集合S(i)。其中每个集合中元素都是一个3元组（F1,F2,x）。这个3元组的每个分量定义为F1:处理机A的完成时间F2：处理机B的完成时间x：任务分配变量。当x i=1时表示将任务i分配给处理机A，当x i=0时表示分配给处理机B。初始时，S(0)=(0,0,0)令F=按处理时间少的原则来分配任务的方案所需的完成时间。例如，当（a1，a2,a3,a4,a5,a6）=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)时，按处理时间少的原则分配任务的方案为（x1,x2,x3,x4,x5,x6）=（1,1,0,1,0,1）因此，F=max2+5+10+2,7+5=19。然后，依次考虑任务i，i=1n。在分配任务i时，只有2种情形，x i=1或x i=0。此时，令S(i)=S(i-1)+(a i,0,2i)US(i-1)+(0,b i,0)在做上述集合并集的计算时，遵循下面的原则：当（a,b,c）,(d,e,f)S(i)且a=d,b仅当maxa,b最后在S(n)中找出使maxF1,F2达到最小的元素，相应的x即为所求的最优解，其最优值为maxF1,F2。当（a1，a2,a3,a4,a5,a6）=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)时,按处理时间少的原则分配任务的方案为（x1,x2,x3,x4,x5,x6）=（1,1,0,1,0,1）因此，F=max2+5+10+2,7+5=19。S(0)=(0,0,0);S(1)=(2,0,2),(0,3,0)S(2)=(7,0,6),(5,3,4),(2,8,2),(0,11,0)S(3)=(14,0,14),(12,3,12),(9,8,10), (7,4,6),(5,7,4),(2,12,2),(0,15,0)S(4)=(19,8,26), (17,4,22),(15,7,20),(12,12,18),(14,11,14),(9,19,10),(7,15,6),(5,18,4)S(5)=(19,11,46), (12,15,38),(19,11,26), (17,7,22),(15,10,20),(12,15,18),(14,14,14),(7,18,6)S(6)=(14,15,102),(19,7,86),(17,10,84),(14,15,82), (9,18,70),(12,19,38),(15,14,20),(12,19,18) max(F1,F2)最小的元组为(14,15,102),(14,15,82),(15,14,20)所以，完成所有作业最短时间是15，安排有三种：（1,1,0,0,1,1），（1,0,0,1,0,1）,(0,1,0,1,0,0)（思路五）C+ 源代码如下:#includeusingnamespace std;constint MAXS = 70;constint MAXN = 10;bool pMAXSMAXSMAXS;int aMAXS,bMAXS;int schduleDyn(int * a,int * b,int n,int mn) int i,j,k;/=数组初始化=for(i = 0; i for(j = 0; j = 0)pijk = pi - ak-1jk-1;if( (j - bk-1) = 0)pijk = (pijk | pij-bk-1k-1);/=求结果=int rs = mn;int temp = 0;for(i = 0; i for(j = 0; j if(pijn) temp = i j ? i : j;if(temp rs = temp;return rs;void main()int i,n,m = 0,mn = 0;/=初始化=cin n;for(i = 0; i cin ai;if(ai m)m = ai;for(i = 0; i cin bi;if(bi m)m = bi;mn = m * n; - 让每个人平等地提升自我！ 106 /=动态规划求解= cout 对于例子: n = 6 ;(a1,.,a6) = (2 5 7 10 5 2),(b,1,b6) = (3 8 4 11 3 4); 由于求解过程比较繁锁,这里只说个大概算法执行过程,首先,用pijk,记录下对于第k 个作业,能否在对于a 机器是i 时间以内,对于b 机器是j 时间以内完成,如果能,则把pijk设为true.经过了设置后,求对于n 个作业的所有可能的值为pijn,对min(max(i,j),结果为15.即为所得到的结果.3考虑下面特殊的整数线性规划问题试设计一个解此问题的动态规划算法，并分析算法的时间复杂度。解：方法1.设,21,1,0n i y i 令n i y y x n i i i +=+1,，则上述规划问题转化为：n i y b y a y c i ni i i n i i i 21,1,0,max 2121=，其中n i a a c c i n i i n i =+1,，把i c 看作价值，i a 看作重量，b 看作背包容量。转化为0/1背包问题，所以可以0/1背包问题的动态规划算法来求解。由于n 件物品的0/1背包的时间复杂性是O （2n ），则此时为O （4n ）。方法2.可以看成是另一种背包问题。即b 为背包容量，2,1,0x i 为背包中可以装0，1，或者2件物品，i x 对应的价值为i c ，求在容量b 一定的前提下，背包所容纳的物品的最大价值。也就是参数完全相同的两个0-1背包问题，它们同时制约于背包容量为C 这个条件。在设计算法时可以优先考虑i m ，也就是先判断背包剩下的容量能不能放进去i c ，若可以再判断能否使1=i p ，若可以则就再放入一个i c ，这样就间接满足了2=+=i i i p m x 的条件。（以上各题均来自同学们作业中的思想，仅供参考，自行整理答案。）