问题

在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导 线(i,π(i))将上端接线柱与下端接线柱相连，如图所示。其中π(i)是 {1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任 何1≤i<j≤n，第i条连线和第j条连线相交的充分且必要的条件是π(i)>π(j)。 电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能 多的连线。换句话说，该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最 大不相交子集。

分析

刚开始我不理解最大不相交子集的意思

其实就是求这些布线中最多选几条线使其不相交

我们可用一个二维数组储存上端点到下端点的最大不相交子集

如dp[7][5]代表从上端点7到下端点5这条线左边有几条不相交线路

a[i]表示上端点i对应的下端点坐标

我们可以知道

上端点为1时，dp[1][j]，当j<a[1]（上端点1对应的下端点a[1]）时，dp[1][j]=0,当j>=a[1]时，dp[1][j]=1

上端点i大于1时

若j小于a[i]时，因为不包括i到a[i]这条线，就是说删除i点对结果没有影响，所以就有dp[i][j]=dp[i-1][j]，而dp[i-1]的所有值已算出

若j大于等于a[i]，说明包括了i到a[i]这条线，此时需要比较dp[i-1][a[i]-1]+1与dp[i-1][j]的关系，dp[i][j]=max{dp[i-1][a[i]-1]+1,dp[i-1][j]}

为什么是比较dp[i-1][a[i]-1]+1,dp[i-1][j]呢？

当i与a[i]这条线与已知的最大不相交子集中的其他线路都不相交时，那么此时去掉此条线路的集合就等于dp[i-1][a[i]-1]，所以dp[i][j]=dp[i-1][a[i]]-1]+1

当i与a[i]这条线与已知的最大不相交子集中的其他线路相交时，那么此时将上端点左移一个点不影响，所以dp[i][j]=dp[i-1][j]

所以我们可以直接比较得到dp[i][j]的最大值并保存。

代码并不复杂，难在理解

代码实现

#include<stdio.h>#include<string.h>#define N 100int main(){int i,j,n;int a[N],dp[N][N];printf("请输入端点个数：");scanf("%d",&n);printf("请输入各端点对应的下端点：");for(i=1;i<=n;i++){scanf("%d",&a[i]);} for(i=1;i<=n;i++){//上端点为1的情况 if(i<a[1]) dp[1][i]=0;else dp[1][i]=1;}for(i=2;i<=n;i++){//其他情况 for(j=1;j<=n;j++){if(j<a[i]){//小于対应线的坐标 dp[i][j]=dp[i-1][j];}else{//大于等于 if(dp[i-1][j]>dp[i-1][a[i]-1]+1){//更新dp最大值 dp[i][j]=dp[i-1][j];}elsedp[i][j]=dp[i-1][a[i]-1]+1;}}}printf("%d\n",dp[n][n]);return 0;}

如果觉得《算法设计——电路布线问题（动态规划）》对你有帮助，请点赞、收藏，并留下你的观点哦！