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

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

int Traceback(int C[],int size[][20],int n,int Net[])//構(gòu)造最優(yōu)解(從最后一項開始構(gòu)造)
{
    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的目的是為了構(gòu)造第一條線路是否入選，應(yīng)為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);//構(gòu)造最優(yōu)解

    printf("最優(yōu)解矩陣：\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("最優(yōu)線路：\n");
    for(i=0;i<k;i++)
        printf("%d ",Net[i]);
    printf("\n");


    return 0;
}