在一块电路板的上、下两端分别有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:二维表数组*/void mnset(int C[],int n,int *size){int i,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:最大子集数*/void traceBack(int C[], int *size, int n, int Net[], int &m){int i,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、测试代码int main(){int n;//接线数目int num;//最大子集数int *l;//接线方式int *p;//子集数int *size;//二维表数组cout << "请输入电路的接线柱数:";cin >> n;//动态创建热线方式数组l = new int[n+1];//动态创建子集数组p = new int[n+1];//临时动态创建二维数组int **temp;temp=new int*[n+1];for(int i=0;i<n+1;i++){temp[i]=new int[i+1];}//将二维表二维数组以一维指针赋给sizesize = &temp[0][0];cout << "请依次输入连接数：" << endl;for(int i=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(int i = 0;i<num;i++)cout << p[i] << " --> "<< l[p[i]] << endl;system("pause");return 0;}