搜索
5-1凸多边形最优三角剖分问题//3d5凸多边形最优三角剖分#includestdafx.h#includeiostreamusingnamespacestd;constintN=7;//凸多边形边数+1intweight[][N]={{0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1},{4,3,4,2,1,0}};//凸多边形的权intMinWeightTriangulation(intn,int**t,int**s);voidTraceback(inti,intj,int**s);//构造最优解intWeight(inta,intb,intc);//权函数intmain(){int**s=newint*[N];int**t=newint*[N];for(inti=0;iN;i++){s[i]=newint[N];t[i]=newint[N];}cout此多边形的最优三角剖分值为：MinWeightTriangulation(N-1,t,s)endl;cout最优三角剖分结构为：endl;Traceback(1,5,s);//s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置return0;}intMinWeightTriangulation(intn,int**t,int**s){for(inti=1;i=n;i++){t[i][i]=0;}for(intr=2;r=n;r++)//r为当前计算的链长（子问题规模）{for(inti=1;i=n-r+1;i++)//n-r+1为最后一个r链的前边界{intj=i+r-1;//计算前边界为r，链长为r的链的后边界t[i][j]=t[i+1][j]+Weight(i-1,i,j);//将链ij划分为A(i)*(A[i+1:j])这里实际上就是k=is[i][j]=i;for(intk=i+1;kj;k++){//将链ij划分为(A[i:k])*(A[k+1:j])intu=t[i][k]+t[k+1][j]+Weight(i-1,k,j);if(ut[i][j]){t[i][j]=u;s[i][j]=k;}}}}returnt[1][N-2];}voidTraceback(inti,intj,int**s){if(i==j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout三角剖分顶点：Vi-1,Vj,Vs[i][j]endl;}intWeight(inta,intb,intc){returnweight[a][b]+weight[b][c]+weight[a][c];}5-4数字三角形最短路径#includeiostream#includealgorithm#includestring.h#defineMax101usingnamespacestd;intD[Max][Max];intnum;intMaxSum(intnum){inti,j;for(i=num-1;i=1;i--)for(j=1;j=i;j++){D[i][j]=max(D[i+1][j],D[i+1][j+1])+D[i][j];}returnD[1][1];}intmain(intargc,charconst*argv[]){inti,j;cinnum;for(i=1;i=num;i++)for(j=1;j=i;j++)cinD[i][j];coutMaxSum(num)endl;return0;}5-2游艇租赁问题#includeiostreamusingnamespacestd;#defineN210intcost[N][N];intm[N];intmain(){intn,i,j;while(cinn){for(i=1;in;i++)for(j=i+1;j=n;j++)cincost[i][j];m[1]=0;intmin;for(i=2;i=n;i++){min=cost[1][i];for(j=1;j=i-1;j++){if(cost[j][i]!=0&&m[j]+cost[j][i]min)min=m[j]+cost[j][i];}m[i]=min;}coutm[n]endl;}return0;}5-6合唱队形问题#includeiostream1.usingnamespacestd;2.3.//用于保存子问题最优解的备忘录4.typedefstruct5.{6.intmaxlen;//当前子问题最优解7.intprev;//构造该子问题所用到的下一级子问题序号(用于跟踪输出最优队列)8.}Memo;9.10.//用于递归输出MemoB中的解11.voidDisplay(int*A,Memo*M,inti)12.{13.if(M[i].prev==-1)14.{15.coutA[i];16.return;17.}18.Display(A,M,M[i].prev);19.coutA[i];20.}21.22.//算法主要部分23.voidGetBestQuence(int*A,intn)24.{25.//定义备忘录并作必要的初始化26.Memo*B=newMemo[n];//B[i]代表从A[0]到A[i]满足升序剔除部分元素后能得到的最多元素个数27.Memo*C=newMemo[n];//C[i]代表从A[i]到A[n-1]满足降序剔除部分元素后能得到的最多元素个数28.B[0].maxlen=1;//由于B[i]由前向后构造初始化最前面的子问题(元素本身就是一个满足升序降序的序列)29.C[n-1].maxlen=1;//同样C[i]由后向前构造30.for(inti=0;in;i++)//为前一个最优子问题序号给定一个特殊标识-131.//用于在跟踪路径时终止递归或迭代(因为我们并不知道最终队列从哪里开始)32.{33.B[i].prev=-1;34.C[i].prev=-1;35.}36.37.for(i=1;in;i++)//构造B[n]38.{39.intmax=1;40.for(intj=i-1;j=0;j--)//查看前面的子问题找出满足条件的最优解并且记录41.{42.if(A[j]A[i]&&B[j].maxlen+1max)43.{44.max=B[j].maxlen+1;//跟踪当前最优解45.B[i].prev=j;//跟踪构造路径46.}47.}48.B[i].maxlen=max;//构造最优解49.}50.51.for(i=n-1;i0;i--)52.{53.intmax=1;54.for(intj=i;jn;j++)//从后往前构造这是为了后面在统筹最终解时可以直接用B[i]+C[i]-155.//否则我们得到的最优解始终为B[n-1]+C[n-1]56.{57.if(A[j]A[i]&&C[j].maxlen+1max)//比当前长度更长记录并构造58.{59.max=C[j].maxlen+1;60.C[i].prev=j;61.}62.}63.C[i].maxlen=max;64.}65.66.//遍历i得到最大的B[i]+C[i]-1(-1是因为我们在B[i]和C[i]中均加上了A[i]这个数因此需要减去重复的)67.intmaxQuence=0;//记录当前最优解68.intMostTall;//记录i用于跟踪构造路径69.for(i=0;in;i++)70.{71.if(B[i].maxlen+C[i].maxlen-1maxQuence)72.{73.maxQuence=B[i].maxlen+C[i].maxlen-1;74.MostTall=i;75.}76.}77.78.cout最大合唱队形长度:maxQuenceendl;79.80.//B由前向后构造因此prev指向前面的元素需要递归输出81.Display(A,B,MostTall);82.//C的prev指向后面元素直接迭代输出83.while(C[MostTall].prev!=-1)84.{85.MostTall=C[MostTall].prev;86.coutA[MostTall];87.}88.coutendl;89.90.delete[]B;91.delete[]C;92.}93.intmain()94.{95.//测试96.int*A;97.intn;98.cout请输入合唱队员个数:endl;99.cinn;100.101.A=newint[n];102.cout输入队员身高:endl;103.for(inti=0;in;i++)104.{105.cinA[i];106.}107.GetBestQuence(A,n);108.delete[]A;109.return0;110.}5-7买票问题状态转移方程是f[i]:=min(f[i-1]+t[i],f[i-2]+r[i-1]);{i=2~n}初值f[0]:=0;f[1]:=t[1];constmaxn=1000;vari,j,n:longint;f,t,r:array[0..maxn]oflongint;functionmin(a,b:longint):longint;beginifabthenexit(a);exit(b);end;beginreadln(n);fori:=1tondoread(t[i]);fori:=1ton-1doread(r[i]);f[0]:=0;f[1]:=t[1];fori:=2tondof[i]:=min(f[i-1]+t[i],f[i-2]+r[i-1]);writeln(f[n]);end.伪代码BuyTicks(T,R)1n←length[T]2f[0]←03f[1]←T[1]4fori←2tondo5f[i]←f[i-2]+R[i-1]6iff[i]f[i-1]+T[i]then7f[i]←f[i-1]+T[i]8returnf5-8最大子段和问题#includestdio.h#includemalloc.hintmax_sum(intn,int*a,int*besti,int*bestj){int*b=(int*)malloc(n*sizeof(int));intsum=0;inti=-1;inttemp=0;for(i=0;i=n-1;i++){if(temp0)temp+=a[i];elsetemp=a[i];b[i]=temp;}sum=b[0];for(i=1;i=n-1;i++){if(sumb[i]){sum=b[i];*bestj=i;}}for(i=*bestj;i=0;i--){if(b[i]==a[i]){*besti=i;break;}}free(b);returnsum;}intmain(void){inta[]={-2,1,-4,13,-5,-2,-10,20,100};intlength=sizeof(a)/sizeof(int);intsum=-1;intbesti=-1;intbestj=-1;sum=max_sum(length,a,&besti,&bestj);printf(besti=%d,bestj=%d,max_sum=%d\n,besti,bestj,sum);return0;}5-9装箱问题发现就是0-1背包问题每个物品的体积就是花费同时也是价值，也就是说这题可以转化为在总体积为w下，可以得到最大的价值最后用总体积减去最大的价值就是剩下最少的空间状态转移方程d[j]=max(d[j],d[j-a[i]]+a[i]);