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

1．最大子段和问题：给定整数序列naaa,,,21，求该序列形如jikka的子段和的最大值：jikknjia1max,0max1)已知一个简单算法如下：intMaxsum(intn,inta,int&besti,int&bestj){intsum=0;for(inti=1;i=n;i++){intsuma=0;for(intj=i;j=n;j++){suma+=a[j];if(sumasum){sum=suma;besti=i;bestj=j;}}}returnsum;}试分析该算法的时间复杂性。2)试用分治算法解最大子段和问题，并分析算法的时间复杂性。3)试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。（提示：令1()max,1,2,,jkijnkibjajn）解：1）分析按照第一章，列出步数统计表，计算可得)(2nO2）分治算法：将所给的序列a[1:n]分为两段a[1:n/2]、a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种可能：①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同；②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同；③a[1:n]的最大子段和为两部分的字段和组成，即jnjilnijaaaaa122；intMaxSubSum(int*a,intleft,intright){intsum=0;if(left==right)sum=a[left]0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);intrightsum=MaxSubSum(a,center+1,right);ints_1=0;intleft_sum=0;for(inti=center;i=left;i--){left_sum+=a[i];if(left_sums1)s1=left_sum;}ints2=0;intright_sum=0;for(inti=center+1;i=right;i++){right_sum+=a[i];if(right_sums2)s2=right_sum;}sum=s1+s2;if(sumleftsum)sum=leftsum;if(sumrightsum)sum=rightsum;}returnsum;}intMaxSum2(intn){inta；returnMaxSubSum(a,1,n);}该算法所需的计算时间T(n)满足典型的分治算法递归分式T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)3）设}{max)(1jikkjiajb,则最大子段和为).(maxmaxmaxmaxmax11111jbaanjjikkjinjjikknjni},,,,max{)(11211jjjjjjjaaaaaaaaajb最大子段和实际就是)}(,),2(),1(max{nbbb.要说明最大子段和具有最优子结构性质，只要找到其前后步骤的迭代关系即可。},)1(max{},}{maxmax{},}{max{}{max)(1111111jjjjjikkjijjijjikkjikkjiaajbaaaaaaajb若0)1(jb,jajbjb)1()(；若0)1(jb，jajb)(。因此，计算)(jb的动态规划的公式为：.1},,)1(max{)(njaajbjbjjintMaxSum(int*a，intn){intsum=0,b=0，j=0;for(inti=1;i=n;i++){if(b0)b=b+a[i];elseb=a[i];end{if}if(bsum)sum=b;j=i；end{if}}returnsum;}自行推导，答案：时间复杂度为O（n）。2.动态规划算法的时间复杂度为O（n）（双机调度问题）用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是ia，若由机器B来处理，则所需要的时间是ib。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：)4,3,11,4,8,3(),,,,,(),2,5,10,7,5,2(),,,,,(,6654321654321bbbbbbaaaaaan解：（思路一）删除（思路二）在完成前k个作业时，设机器A工作了x时间，则机器B最小的工作时间是x的一个函数。设F[k][x]表示完成前k个作业时，机器B最小的工作时间，则)}](1[,)](1[min{)]([kkaxkFbxkFxkF其中kbxkF)](1[对应第k个作业由机器B来处理（完成k-1个作业时机器A工作时间仍是x，则B在k-1阶段用时为)](1[xkF）；而)](1[kaxkF对应第k个作业由机器A处理（完成k-1个作业，机器A工作时间是x-a[k]，而B完成k阶段与完成k-1阶段用时相同为)](1[kaxkF）。则完成前k个作业所需的时间为)}]([,max{xkFx1）当处理第一个作业时，a[1]=2,b[1]=3;机器A所花费时间的所有可能值范围：0xa[0].x0时，设F[0][x]=∞，则max(x,∞)=∞；0x2时，F[1][x]=3，则Max(0,3)=3，x2时，F[1][x]=0，则Max(2,0)=2；2）处理第二个作业时：x的取值范围是：0=x=(a[0]+a[1])，当x0时，记F[2][x]=∞；以此类推下去（思路三）假定n个作业的集合为nSn,,2,1。设J为nS的子集，若安排J中的作业在机器A上处理，其余作业在机器B上处理，此时所用时间为JSjjJjjbaJT\,max)(，则双机处理作业问题相当于确定nS的子集J，使得安排是最省时的。即转化为求J使得)}({minJTnSJ。若记1,,2,11nSn，则有如下递推关系：JSjjnJjjSJJSjjJjjnSJISjjIjjSIbbabaabannn\\\,maxmin,,maxminmin,maxmin11－－（思路四）此问题等价于求（x1,……xn），使得它是下面的问题最优解。minmax{x1a1+……xnan，(1-x1)b1+……+(1-xn)bn}xi=0或1，i=1~n基于动态规划算法的思想，对每个任务i，依次计算集合S(i)。其中每个集合中元素都是一个3元组（F1,F2,x）。这个3元组的每个分量定义为F1:处理机A的完成时间F2：处理机B的完成时间x：任务分配变量。当xi=1时表示将任务i分配给处理机A，当xi=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=max{2+5+10+2,7+5}=19。然后，依次考虑任务i，i=1~n。在分配任务i时，只有2种情形，xi=1或xi=0。此时，令S(i)={S(i-1)+(ai,0,2i)}U{S(i-1)+(0,bi,0)}在做上述集合并集的计算时，遵循下面的原则：①当（a,b,c）,(d,e,f)ЄS(i)且a=d,b=e时，仅保留（a,b,c）；②仅当max{a,b}=F时，(a,b,c)ЄS(i)最后在S(n)中找出使max{F1,F2}达到最小的元素，相应的x即为所求的最优解，其最优值为max{F1,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=max{2+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++源代码如下:#includeiostreamusingnamespacestd;constintMAXS=70;constintMAXN=10;boolp[MAXS][MAXS][MAXS];inta[MAXS],b[MAXS];intschduleDyn(int*a,int*b,intn,intmn){inti,j,k;//===========数组初始化===================for(i=0;i=mn;i++)for(j=0;j=mn;j++){p[i][j][0]=true;for(k=1;k=n;k++)p[i][j][k]=false;}//===========动态递归=============for(k=1;k=n;k++)for(i=0;i=mn;i++)for(j=0;j=mn;j++){if((i-a[k-1])=0)p[i][j][k]=p[i-a[k-1]][j][k-1];if((j-b[k-1])=0)p[i][j][k]=(p[i][j][k]|p[i][j-b[k-1]][k-1]);}//================求结果=====================intrs=mn;inttemp=0;for(i=0;i=mn;i++)for(j=0;j=mn;j++){if(p[i][j][n]){temp=ij?i:j;if(temprs)rs=temp;}}returnrs;}voidmain(){inti,n,m=0,mn=0;//=============初始化========================cinn;for(i=0;in;i++){cina[i];if(a[i]m)m=a[i];}for(i=0;in;i++){cinb[i];if(b[i]m)m=b[i];}mn=m*n;//=========动态规划求解