算法第五章作业

算法第五章作业张杰20130713班2013E80186611331．最大子段和问题：给定整数序列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);intleft_sum=0;for(inti=center;i=left;i--){left_sum+=a[i];if(left_sum0)left_sum=0;}intright_sum=0;for(inti=center+1;i=right;i++){right_sum+=a[i];if(right_sum0)right_sum=0;}sum=left_sum+right_sum;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,即},,,,max{)(11211jjjjjjjaaaaaaaaajb那么问题的答案就在)}(,),2(),1(max{nbbb.而对于b(j)和b(j-1)，二者有如下关系},)1(max{},}{maxmax{},}{max{}{max)(1111111jjjjjikkjijjijjikkjikkjiaajbaaaaaaajb所以有最优子结构性质，动态规划的公式为.1},,)1(max{)(njaajbjbjjintMaxSum(int*a，intn){intb[n]=0;intsum=0;b[1]=a[1];for(inti=2;i=n;i++){if(b[i-1]0)b[i]=b[i-1]+a[i];elseb[i]=a[i];if(b[i]sum)sum=b[i];}returnsum;}容易得到时间复杂度为O（n）2.（双机调度问题）用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是ia，若由机器B来处理，则所需要的时间是ib。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：)4,3,11,4,8,3(),,,,,(),2,5,10,7,5,2(),,,,,(,6654321654321bbbbbbaaaaaan解：设)(iT为完成前i个作业，系统所需的最短处理时间，]}[],[max{)(isisiTba][iSa表示在完成前i个作业所需时间最少的策略下，分配到A机器上处理的作业的时间，][iSb表示在完成前i个作业所需时间最少的策略下，分配到B机器上处理的作业的时间得到)(iT的递推公式}}]1[,]1[min{),1(max{)(ibiabiSaiSiTiT，其中]}[],[max{)(isisiTba。直接的关系式即是，　　　　且　　　且　　　　　)1()1()1(},min{)1()(iTaSbSaSaSiTbSaSbSbSiTbSaSiTiTiaibiaiaibiaibibibia，其中为了方便，]1[iSSaa，]1[iSSbb得到算法如下：intminTime(int*a,int*b,intn)//a,b为A,B机器上处理作业所用时间数组{intsa=0;//sa表示分配到A机器上处理的作业的最短总时间intsb=0;//sb表示分配到B机器上处理的作业的最短总时间intT=0;//T为最短总的处理时间for(inti;in;i++){if((sa+a[i]sb+b[i])&&(sa+a[i]T))//式(1)中的情况3{sa+=a[i];T=sa;}elseif((sb+b[i]sa+a[i])&&(sb+b[i]T))//式(1)中的情况2{sb+=b[i];T=sb;}Else//式(1)中的情况1{if((sa+a[i]sb+b[i])&&(sa+a[i]T))sa+=a[i];else((sb+b[i]sa+a[i])&&(sb+b[i]T))sb+=b[i];}}returnT;}算法的时间复杂度为O(n)。用题中的实例分析算法n=6,(a1,a2,a3,a4,a5,a6)=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)i=1,满足式中(1)中的第三条，得：sa=2,sb=0,T=2;i=2,满足式中(1)中的第三条，得：sa=7,sb=0,T=7;i=3,满足式中(2)中的第三条，得：sa=7,sb=4,T=7;i=4,满足式中(2)中的第三条，得：sa=7,sb=15,T=15;i=5,满足式中(1)中的第三条，得：sa=12,sb=15,T=15;i=6,满足式中(1)中的第三条，得：sa=14,sb=15,T=15;得到最短的T为15。3.考虑下面特殊的整数线性规划问题nixbxaxciniiiniii1},2,1,0{,max11试设计一个解此问题的动态规划算法，并分析算法的时间复杂度。解：设,21},1,0{niyi令niyyxniii1,，则上述规划问题转化为：niybyayciniiiniii21},1,0{,,max2121，其中niaacciniini1,,，把ic看作价值，ia看作重量，b看作背包容量。转化为0/1背包问题，所以可以0/1背包问题的动态规划算法来求解。由于n件物品的0/1背包的时间复杂性是O（2n），则此时为O（4n）。4.可靠性设计：一个系统由n级设备串联而成，为了增强可靠性，每级都可能并联了不止一台同样的设备。假设第i级设备Di用了mi台，该级设备的可靠性是gi(mi)，则这个系统的可靠性是Πgi(mi)。一般来说gi(mi)都是递增函数，所以每级用的设备越多系统的可靠性越高。但是设备都是有成本的，假定设备Di的成本是ci，设计该系统允许的投资不超过c，那么，该如何设计该系统（即各级采用多少设备）使得这个系统的可靠性最高。试设计一个动态规划算法求解可靠性设计问题。解：问题描述：niiimg1)(max约束条件：nniiiiniicccmccm1111,记)]([xkG为第k级设备在可用投资为x时的系统可靠性最大值则有如下关系式)}](1[)({)]([max1kkkkcxmmcxkGmgxkGkk定义下列函数elsecxcxGnii,,1)](0[1cxmcxGmgcxcmcxGmgcxxGccmniicxmnii)},](0[)({)},](0[)({,)](1[111111111111maxmax1111nkiikkkkcccxmnkiicxmcxkGmgcxxkGkk)},](1[)({,)]([max),min(11初始计算)](0[cG，依次求解，即可得出策略集。令niiccc1，1iimm，则转化问题描述：niiimg1)(max约束条件：nniiiiniicccmccm110,elseccxgxGniniii,0),1()](0[1111111),min(11)},](0[)({,)](1[max111cxmcxGmgcxxGcccxmkkkkkcccxmkcxmcxkGmgcxxkGkk)},](1[)({,)]([max),min(11