在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱i与下端接线柱π(i)相连，如下图。其中，π(i),1≤i<≤n,是｛1,2,…,n｝的一个排列。导线(I,π(i))称为该电路板上的第i条连线。对于任何1≤i≤j≤n,第i条连线和第j条连线相交的充要条件是π(i)>π(j).在制作电路板时，要求将这n条线分布到若干个绝缘层上，在同一层上的连线不能相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets=｛i，π(i)，1≤i≤n｝的最大不想交子集。
问题分析
1、最优子结构性质记N(i,j)={t|(t,π(i))∈Nets,t≤i,π(t)≤j}.N(i,j)的最大不相交子集为MNS（i,j）。Size(i,j)=|MNS(i,j)|。
2、当i=1时
3、当i>1时，j<π(i拘七呷憎)。此时，(i,π(i))不属于N(i,j)。故在这种情况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,枣娣空郅j).j≥π(i)。此时，若(i,π(i))∈MNS(i,j)，则对任意(t,π(i))∈MNS(i,j)有t<i且π(t)<π(i)；否则，(t,π(t))与(i,π(i))相交。在这种情况下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。否则，子集MNS(i-1,π(i)-1)∪{(i,π(i))}包含于N(i,j)是比MNS(i,j)更大的N(i,j)的不相交子集。这与MNS(i,j)的定义相矛盾。若(i,π(i))不属于MNS(i,j)，则对任意(t,π(t))∈MNS(i,j)，有t<i。从而MNS(i,j)包含于N(i-1,j)，因此，Size(i,j)≤Size(i-1,j).另一方面，MNS(i-1,j)包含于N(i,j),故又有Size(i,j)≥Size(i-1,j)，从而Size（i,j）=Size(i-1,j).
4、递归计算最优值经以上后分，可电路布线问题的最优值为Size(n,n)。由该问题的最优子结构性质可知：
5、根据上面递归式可以得到二维表：
6、红色标明的就是算法选择的路径（向上优先，也可以用向左优先，答案都是四个，但值会有一点不同）。在斜角值改变时可以取得所求的子集。即9->10,7->9,5->5,3->4
C++源码实现
1、/**计算最优值*输入参数C[]:接线方式*输入参数n:接线柱数*输入参数size:二维表数组*/voidmnset(intC[],intn,int*size){inti,j;//当i=1时for(j=0;j<C[1];j++){size[n+j]=0;}for(j=C[1];j<=n;j++){size[n+j]=1;}//当i>=2时for(i=2;i<n;i++){for(j=0;j<C[i];j++){size[i*n+j]=size[(i-1)*n+j];}for(j=C[i];j<=n;j++){size[i*n+j]=max(size[(i-1)*n+j],size[(i-1)*n+C[i]-1]+1);}}size[n*n]=max(size[(n-1)*n],size[(n-1)*n+C[n-1]-1]+1);}
2、/**构造最优值*输入参数C:接线方式*输入参数size:二维表数组*输入参数n:接线柱数*输入参数Net:最大子集数组*输入参数m:最大子集数*/voidtraceBack(intC[],int*size,intn,intNet[],int&m){inti,j=n;m=0;for(i=n;i>1;i--){if(size[i*(n+1)+j]!=size[(i-1)*(n+1)+j]){Net[m++]=i;j=C[i]-1;}}if(j>=C[1]){Net[m++]=1;}}
3、测试代码intmain(){intn;//接线数目intnum;//最大子集数in隋茚粟胫t*l;//接线方式int*p;//子集数in墉掠载牿t*size;//二维表数组cout<<"请输入电路的接线柱数:";cin>>n;//动态创建热线方式数组l=newint[n+1];//动态创建子集数组p=newint[n+1];//临时动态创建二维数组int**temp;temp=newint*[n+1];for(inti=0;i<n+1;i++){temp[i]=newint[i+1];}//将二维表二维数组以一维指针赋给sizesize=&temp[0][0];cout<<"请依次输入连接数："<<endl;for(inti=1;i<=n;i++)cin>>l[i];//调用计算最优值函数mnset(l,n+1,size);//调用构造最优值函数traceBack(l,size,n,p,num);//打印子集数cout<<"最大不想交子集数："<<num<<endl<<endl;//打印出子集cout<<"最大不想交子集"<<endl;for(inti=0;i<num;i++)cout<<p[i]<<"-->"<<l[p[i]]<<endl;system("pause");return0;}