在制作電路板時，要求將這n條線分布到若干個絕緣層上，在同一層上的連線不能相交。電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導線集Nets = ｛i，π(i)，1 ≤ i ≤ n｝的最大不想交子集。
         書上解決這個問題的時候用了很多集合的概念，我花了一上午的時間去理解，結果沒理解啥意思！！！最后還是結合遞歸式和代碼看懂他說的最優子結構性質這一段基本意思。。
         定義了一個Size[i][j]二維數組，代表從上端點1，下端點1到上端點i，下端點j之間的最優解。在這樣的定義下我們可以求得size[1][j],然后根據定義求得數組上其他值！！最后Size[n][n]就是所求解！！在遞推Size[i][j]時，要抓住i條線路在最優解內和不在最優解內做判斷。
代碼如下：

#include<windows.h>
#include<stdio.h>
#include<windef.h>
#include<string.h>
void MNS(int C[],int n,int size[][20])
{
    int i,j;
    for(j=0;j<C[1];j++)    //初始化
    {
        size[1][j]=0;
    }

    for(j=C[1];j<=n;j++)//初始化
    {
        size[1][j]=1;
    }

    for(i=2;i<n;i++)        //n>i>=2
    {
        for(j=0;j<C[i];j++)    //j<C[i]時第i條線路必然不在最優解內
            size[i][j]=size[i-1][j];

        for(j=C[i];j<=n;j++)
            size[i][j]=max(size[i-1][j],size[i-1][C[i]-1]+1);//取第i條線路在最優解內和不在最優解內的較大值
    }

    size[n][n]=max(size[n-1][n],size[n-1][C[n]-1]+1);//書上總喜歡把最后一項單獨計算.有時候是有問題的，就像0-1背包，雖然節約了時間
}

int Traceback(int C[],int size[][20],int n,int Net[])//構造最優解(從最后一項開始構造)
{
    int j=n,i;
    int m=0;
    for(i=n;i>1;i--)   //1<i<=n
    {
        if(size[i][j]!=size[i-1][j])   //代表第i條入選
        {
            Net[m++]=i;
            j=C[i]-1;    //這里j的目的是為了構造第一條線路是否入選，應為i!=1
        }
    }

    if(j>=C[1])           //入選
        Net[m++]=1;

    return m;
}

int main()
{
    int C[20]={0,8,7,4,2,5,1,9,3,10,6},size[20][20],i,j,n,k;
    int Net[20];

    memset(size,0,sizeof(size));
    memset(Net,0,sizeof(Net));

    MNS(C,10,size);//構造最優解

    printf("最優解矩陣：\n");
    n=10;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            printf("%d ",size[i][j]);
        }
        printf("\n");
    }

    k=Traceback(C,size,n,Net);
    
    printf("最優線路：\n");
    for(i=0;i<k;i++)
        printf("%d ",Net[i]);
    printf("\n");


    return 0;
}