算法材料

6-17,最佳装载问题是将一批集装箱装上一艘载重为C的轮船，其中集装箱i的重量为wi(0=i=n-1),最优装载问题是指在装载体积不受限制的情况下,求使得装箱数目最多的装载方案.(1)按贪心策略的要求,给出关于上述最优化问题的形式化描述.(2)给出贪心法求解这一问题的最优量度标准;(3)讨论其最优解的最优子结构.(4)编写装箱问题的贪心算法;(5)设有重量为(4,6,3,5,7,2,9)的7个集装箱，轮船载重为26,求最优解.解;(1),形式化描述如下：给定C0,wi010ni求X=(10}1,0{)...,,(1210nixxxxxin)使得Cwxniii10并且使10niix最大（2）以重量作为最优量度标准，以重量最轻者先装来选择集装箱装上船（3）设(x0,x1,----xn-1)是最优装载问题的最优解，则易知(x1,x2,----xn-1)是轮船载重为C-x0w0且待装船的集装箱为{1，3----n-1}时相应最优装载问题的一个最优解，即最优装载问题具有最优子结构特性。否则，假设(x1,x2,----xn-1)不是子问题的最优解，假设有另一个解Z=(z1,z2,----zn-1)是子问题的最优解，则有：则：iniinizxxx110110且Czwwxinii1100，即(x0，z1,z2,--zn-1)是最优装载问题的最优解,与(x0,x1,----xn-1)是最优装载问题的最优解矛盾，所以,(x1,x2,----xn-1)是子问题的最优解,故最优装载问题具有最优子结构特性。(4)参考程序1/*箱子信息结构体*/structgoodinfo{floatw;/*箱子重量*/intX;/*箱子存放的状态*/intflag;/*箱子编号*/};/*按物品重量做升序排列*/voidsort(goodinfogoods[],intn){intj,i;for(j=2;j=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].wgoods[i].w),00111111xwCzwzxiniiiniini且{goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}}/*用贪心法对物品进行选择装入*/voidloading(goodinfogoods[],floatM,intn){floatcu;inti,j;intA=0;/*对装入箱子进行计数*/for(i=1;i=n;i++)/*赋初值*/goods[i].X=0;cu=M;/*船的剩余载重*/for(i=1;in;i++){if(goods[i].wcu)/*当该箱重量大于剩余载重跳出*/break;goods[i].X=1;A++;cu=cu-goods[i].w;/*确定船的剩余载重*/}for(j=2;j=n;j++)/*对箱子按序号大小作升序排列*/{goods[0]=goods[j];i=j-1;while(goods[0].flaggoods[i].flag){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}cout①最优解为:endl;/*输出*/for(i=1;i=n;i++){cout第i件物的存放状态:;coutgoods[i].Xendl;}cout0：未装入；1：装入endl;coutendl;cout②最多能装入的箱子数为:;coutAendl;}(5)首先，选择最优量度标准为重量;其次,依据集装箱重量的非减次序对输入(物品)进行排序对集装箱的排序结果为:5,2,0,3,1,4,6最后，进行贪心选择:X=(5)X=(5,2)X=(5,2,0)(剩余载重)U=24U=21U=17X=(5,2,0,3)X=(5,2,0,3,1)X=(5,2,0,3,1)(剩余载重)U=12U=6所以，最优解为X=(0,1,2,3,5),最优解值为57-5设有4个矩阵连乘积ABCD：A:45*8,B:8*40,C:40*25,D:25*10,,请求出它们的最优计算次序和计算量。解：p0=45，p1=8，p2=40，p3=25，p4=10可只给出矩阵形式计算m矩阵为：m[0][1]=p0*p1*p2=45*8*40=14400;m[1][2]=p1*p2*p3=8*40*25=8000;m[2][3]=p2*p3*p4=40*25*10=11250;m[0][2]=m[0][0]+m[1][2]+p0*p1*p3=8000+45*8*25=8000+9000=17000=m[0][1]+m[2][2]+p0*p2*p3=14400+45*40*25=14400+45000m[1][3]=m[1][1]+m[2][3]+p1*p2*p4=11250+8*40*10=11250+3200=m[1][2]+m[3][3]+p1*p3*p4=8000+8*25*10=10000m[0][3]=m[0][0]+m[1][3]+p0*p1*p4=10000+45*8*10=10000+3600=13600=m[0][1]+m[2][3]+p0*p2*p4=14400+11250+45*40*10==m[0][2]+m[3][3]+p0*p3*p4=17000+45*25*10=17000+11250=28250这4个矩阵相乘需要的最小数量乘法的次数=13600最优计算次序A（（BC）D）7-9给定字符串A=“xzyzzyx”和B=“zxyyzxz”，使用LCS算法求最长公共子串，并给出一个最长公共子串。提示：从上到下，从左往右计算C矩阵，依据C矩阵，求得最长公共子序列0144001700013600m=080001000001125000000s=112223解：计算求得C矩阵如下，依矩阵C可求得两个最长公共子序列分别为xyzz和zyyx（求一个即可）7-17设流水作业调度的实例为n=7，(a0,a1,a2,a3,a4,a5,a6)=(6,2,4,1,7,4,7),(b0,b1,b2,b3,b4,b5,b6)=(3,9,3,8,1,5,6).请使用流水作业调度的Johnson算法求使完成时间最小的最优调度,并求该最小完成时间。提示：依据调度规则，求得最优调度次序解:；令mi=min{ai，bi}0=i7即得:m0=b0=3,m1=a1=2,m2=b2=3,m3=a3=1,m4=b4=1,m5=a5=4m6=b6=6考虑mi,对其从小到大排序得(m3,m4,m1,m0,m2,m5,m6)考虑mi序列(如果序列中下一个数mi是ai,则作业i放在最左的空位，否则，作业i放在最右的空位)得:最优调度顺序(3,1,5,6,2,0,4)依据最优调度在两台处理机上处理作业，最小完成时间:36(画出如教材P170的图7-17的形式即可求得最小完成时间36)6-1设有背包问题实例，n=7，(w0,w1,w2,w3,w4,w5,w6)=(2,3,5,7,1,4,1)，(p0,p1,p2,p3,p4,p5,p6)=(10,5,15,7,6,18,3)，M=15。求这一实例的最优解及最大收益.解:首先，选择最优量度标准为收益重量比;其次,依据收益重量比的非增次序对输入(物品)进行排序(p0/w0,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6)=(5,5/3,3,1,6,4.5,3)对物品排序结果为:4,0,5,2,6,1,3最后，进行贪心选择:X=(4)X=(4,0)X=(4,0,5)(剩余载重)U=14U=12U=8(收益)P=6P=6+10=16P=16+18=34X=(4,0,5,2)X=(4,0,5,2,6)X=(4,0,5,2,6,1(2/3))(剩余载重)U=3U=2U=0(收益)P=34+15=49P=49+3=52P=52+2/3*5=55.33所以,最优解为x=(1,2/3,1,0,1,1,1);即装入第0,2,4,5,6物品和第1个物品的2/3最大收益:P=55.336-2,0/1背包问题是一种特殊的背包问题，装入背包的物品不能分割,只允许或者整个物品装入背包，或者不装入，即xi=0,或1,(0=in),以题6-1的数据作为0/1背包的实例，按贪婪法求解，这样求得的解一定是最优解吗?为什么?解:首先，选择最优量度标准为收益重量比;其次,依据收益重量比的非增次序对输入(物品)进行排序(p0/w0,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6)=(5,5/3,3,1,6,4.5,3)对物品排序结果为:4,0,5,2,6,1,3最后，进行贪心选择:X=(4)X=(4,0)X=(4,0,5)(剩余载重)U=14U=12U=8(收益)P=6P=6+10=16P=16+18=34X=(4,0,5,2)X=(4,0,5,2,6)X=(4,0,5,2,6)(剩余载重)U=3U=2继续考察第1和第3个(收益)P=34+15=49P=49+3=52物品,都不能装入.所以,贪心法求得的0/1背包问题的最优解为x=(1,0,1,0,1,1,1);即装入第0,2,4,5,6物品最大收益:P=52但实际上，当y=(1,1,1,0,1,1,0)即装入第0,1,2,4,5物品,可获收益为P=54,所以，贪心法求得的0/1背包问题的解x一定不是最优解.原因是:对于0/1背包问题，贪心法并不能保证使其单位载重下的收益最大，因为通常在背包没还装满时，却再也装不下任何物品，这样，就使得单位载重下的物品收益减少,所以，0/1背包问题通常不能用贪心法求解.6-3设有带时限的作业排序实例n=7，收益(p0,p1,p2,p3,p4,p5,p6)=(3,5,20,18,1,6,30)，作业的时限(d0,d1,d2,d3,d4,d5,d6)=(1,3,4,3,2,1,2),给出以此实例为输入，执行函数JS得到的用最优解和最大收益。解:X={5,6,3,2}最大收益为74函数JS如下:intJS(int*d,int*x,intn){//设p0≥p1≥…≥pn1intk=0;x[0]=0;for(intj=1;jn;j++){//O(n)intr=k;while(r=0&&d[x[r]]d[j]&&d[x[r]]r+1)r--;//搜索作业j的插入位置if((r0||d[x[r]]=d[j])&&d[j]r+1){//若条件不满足，选下一个作业for(inti=k;i=r+1;i--)x[i+1]=x[i];//将x[r]以后的作业后移x[r+1]=j;k++;//将作业j插入r+1处}}returnk;}在执行JS函数之前，必须先对输入(即作业)按作业的收益非增次序排序，结果为:6,2,3,5,1,0,4接着执行JS函数:最初,解集合X为空.首先,考虑作业6,假设将其加入集合X,即x[0]=6;考虑X中的作业能否均如期完成,因为此时X中只有作业6,其截止时限为2,故,能如期完成,此时,将作业6加入作业子集X中,此时，子集X中的最大可用下标k=0;接着，考虑作业2.首先搜索作业2在X集合中的插入位置，使得X集合中的元素按作业的截止时限的非减次序排序,因为d6=2,而d2=4,所以，可将作业2插在作业6的后面，即x[1]=2,得到X=(6,2),考虑X中的作业能否均如期完成?因为d6=2=1,d2=4=2,所以，X中作业均能如期完成，将作业2加入子集X中.子集X中的最大可用下标k=k+1=1考虑作业3.首先搜索作业3在X集合中的插入位置，使得X集合中的元素按作业的截止时限的非减次序排序,因为d6=2,d2=4,而d3=3所以，可将作业3插在作业6的后面,作业2的前面，得到X=(6,3,2),666262632X:0123456k0123456X:X:0123456X:k