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

int Traceback(int C[],int size[][20],int n,int Net[])//構(gòu)造最優(yōu)解(從最后一項(xiàng)開(kāi)始構(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;
}