电路布线.txt

用动态规划算法解决电路分布问题

/*
    电路布线问题_DP算法 Created By guoliqiang 2008.12.18
    dp【i】【j】表示上面第1-i个接线柱，下面第1-j个接线柱，这个范围内不相交布线的最大条数
    dp【i】【j】=max{dp【i-1】【j】，dp【i】【j-1】} when j！=a【i】
                =max{dp【i-1】【j】，dp【i】【j-1】}+1 when j==a【i】
    下面的代码在迭代上有所改动，但和上面迭代式的意思相同。
*/
#include<stdio.h>
#include<string.h>
#define N 10
int a[N+1]={0,8,7,4,2,5,1,9,3,10,6};
int dp[N+1][N+1];
int max(int ,int);
void TB(int,int);
int main()
{
    memset(dp,0,(N+1)*(N+1)*sizeof(int));
    for(int i=1;i<=N;i++)
    {
        if(i<a[1])
        {dp[1][i]=0;}
        else
        {dp[1][i]=1;}
    }
    for(int i=2;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(j<a[i])
            {
                dp[i][j]=dp[i-1][j];
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][a[i]-1]+1);
            }
        }
    }
    printf("最大不相交布线条数为：%d\n",dp[10][10]);
    printf("其布线分别为：\n");
    TB(10,10);
    return 0;
}
void TB(int m,int n)
{
    if(m==0||n==0)return;
    if(dp[m][n]==dp[m-1][n])
    {
        TB(m-1,n);
    }
    else
    {
        printf("%d:%d\n",m,a[m]);
        TB(m-1,a[m]-1);
    }
}
int max(int a,int b)
{
    return a>b?a:b;
}