北航研究生-算法设计与分析大作业一

一、请安排投资计划，使总的利润最大。写出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步骤及结果。解：设k表示前k个项目；状态变量为kx，表示能投资到前k个项目中的金额为kx；决策变量为}0|{,kkkkkkxuuDDu，表示将ku的金额投入到第k个项目中；状态转移方程为kkkuxx1，表示能投资到前k+1个项目的金额等于能投资到前k个项目的金额，加上投资到第k+1个项目的金额；指标函数为)(Pkkx，表示将kx投入到前k个项目中所能获得的最大利润；设)(Akkx为向第k个项目投资kx金额所能获得的利润。则递推关系式为：)}(A)({Pmax)(P00,0)(P1kkkkkDukkkkkuuxxxkxkk或①当k=0或0kx时，总利润一定为0②当k=1时，8万元只投资第一个项目，有1x012345678)(P11x05154080909598100若将8万元只投资第一个项目，则将所有8万都投入可获得最大利润100万③当k=2时，8万元只投资第一、第二个项目，有若将0万投资第一个项目，8万投资第二个项目，利润为0+75=75若将1万投资第一个项目，7万投资第二个项目，利润为5+74=79若将2万投资第一个项目，6万投资第二个项目，利润为15+73=88若将3万投资第一个项目，5万投资第二个项目，利润为40+70=110若将4万投资第一个项目，4万投资第二个项目，利润为80+60=140若将5万投资第一个项目，3万投资第二个项目，利润为90+40=130若将6万投资第一个项目，2万投资第二个项目，利润为95+15=110若将7万投资第一个项目，1万投资第二个项目，利润为98+5=103若将8万投资第一个项目，0万投资第二个项目，利润为100+0=100此时将4万元投资第一个项目，将剩余4万元投资第二个项目可获得最大利润140万元同时计算出将2x万元投资到前两个项目的获利情况如下表：2x012345678)(P22x051540809095120140④当k=3时，8万元同时投资第一、第二、第三个项目，有若将0万投资前两个项目，8万投资第三个项目，利润为0+53=53若将1万投资前两个项目，7万投资第三个项目，利润为5+52=57若将2万投资前两个项目，6万投资第三个项目，利润为15+51=66若将3万投资前两个项目，5万投资第三个项目，利润为40+50=90若将4万投资前两个项目，4万投资第三个项目，利润为80+45=125若将5万投资前两个项目，3万投资第三个项目，利润为90+40=130若将6万投资前两个项目，2万投资第三个项目，利润为95+26=121若将7万投资前两个项目，1万投资第三个项目，利润为120+4=124若将8万投资前两个项目，0万投资第三个项目，利润为140+0=140此时将4万元投资第一个项目，将剩余4万元投资第二个项目，第三个项目投资0元，可获得最大利润140万元。计算出将3x万元投资到三个项目的获利情况如下表代码：3x012345678)(P33x0526408090106120140#includestdio.h#defineM4//项目数加1#defineN9//投资金额数加1intmain(){intA[M][N]={{0,0,0,0,0,0,0,0,0},{0,5,15,40,80,90,95,98,100},{0,5,15,40,60,70,73,74,75},{0,4,26,40,45,50,51,52,53}};intP[M][N];//将N金额投资到前M个项目所获的最大利润for(intk=0;kM;k++)for(intj=0;jN;j++){if(k==0||j==0)P[k][j]=0;else{intmaxP=0;for(intv=0;v=j;v++){//决策变量，将v金额投资到前k-1个项目，剩余//额投资到第k个项目if(P[k-1][v]+A[k][j-v]maxP)maxP=P[k-1][v]+A[k][j-v];}P[k][j]=maxP;//将j金额投资到前k个项目获得的最大利润}}printf(将不同金额(0~8万元)投资到三个项目中的获利情况\n);for(intj=0;jN;j++){printf(%d\t,P[3][j]);//将金额j投资到三个项目中的获利，最终求的是P[3][8]}printf(\n将8万元投资到三个项目中的最大获利为%d\n,P[3][8]);return0;}结果：二、要求：写出递推关系式、伪代码和程序相关说明，并分析时间复杂性。（请遵守第一节课提出的有关assignment的要求：提交的可执行程序必须能够输出结果，源代码必须可编译等等）设]][[totalji为从顶点},...,,{1jiivvv所构成的多边形划分成互不重叠的三角形后，各三角形的权重之和最小的权重之和；]][[jiD为顶点iv和顶点jv的边的权重。设顶点iv和顶点jv之间有一个顶点kv，其中jki，则},...,,{1jiivvv所构成的多边形的总权重]][[totalji由三部分组成，一是由顶点},...,{kivv所构成的多边形的总权重]][[totalki，二是由顶点},...,{jkvv所构成的多边形的总权重]][[totaljk，三是由顶点iv、kv、jv所构成的三角形的权重]][[]][[]][[kiDjkDkiD，取不同的k，直到找到总权重的最小值，递推关系式为：]}][[]][[]][[]][[]][[{min1,0]][[jiDjkDkiDjktotalkitotaljijijitotaljki或根据递推关系式可求得权重之和]][[totalji为：顶点1v2v3v4v5v6v7v8v1v00571081611962442772v00521141671902333v00551021401914v0059921485v00421026v00607v008v0故最优分割后各三角形的权重和为277伪代码为：输入：顶点数E=8,以及两两顶点之间的距离矩阵D[i][j]。(为了编程方便下标都从0开始)输出：将多边形分割成互不重迭的三角形，各三角形的权重之和的最小值total[E][E]={0};ford=2toE-1step1doforj=0toE-d-1step1domint=inf;fork=j+1toj+d-1step1doif(total[j][k]+total[k][j+d]+D[j][k]+D[k][j+d]+D[j][j+d]mint)thenmint=total[j][k]+total[k][j+d]+D[j][k]+D[k][j+d]+D[j][j+d];endifendfortotal[j][j+d]=mint;endforendforprint(\n各三角形的权重之和最小为：%d\n,total[0][7]);时间复杂度)()2)(()(f312nOddnnnd代码为：//代码中增加了输出弦的集合的算法#includestdio.h#defineE8#defineMAX9999999//递归地输出各条弦voidEdges(intvex[][E],inti,intj){if(i==j||j==i+1)return;intk=vex[i][j];if(!(i==0&&j==E-1))printf((%d,%d),i,j);Edges(vex,i,k);Edges(vex,k,j);}//主程序，求最小权重总和intmain(){intD[][E]={{0,14,25,27,10,11,24,16},{0,0,18,15,27,28,16,14},{0,0,0,19,14,19,16,10},{0,0,0,0,22,23,15,14},{0,0,0,0,0,14,13,20},{0,0,0,0,0,0,15,18},{0,0,0,0,0,0,0,27},{0,0,0,0,0,0,0,0}};inttotal[E][E]={0};//total[i][j]表示从顶点i到顶点j的各三角形的权重之和最小值intvex[E][E]={0};//vex[i][j]表示顶点i到顶点j的中间节点，三者构成一个最小权重三角形for(intd=2;dE;d++){for(intj=0;jE-d;j++){intmint=MAX,ik;for(intk=j+1;kj+d;k++){if(total[j][k]+total[k][j+d]+D[j][k]+D[k][j+d]+D[j][j+d]mint){mint=total[j][k]+total[k][j+d]+D[j][k]+D[k][j+d]+D[j][j+d];ik=k;}}total[j][j+d]=mint;vex[j][j+d]=ik;}}printf(\n各三角形的权重之和最小为：%d\n,total[0][7]);printf(\n弦的集合为：\n);Edges(vex,0,E-1);printf(\n);return0;}输出结果为：各节点之间的连线为：