《算法设计与分析》 --王晓东
题目描述：
在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,a(i))将上端接线柱与下端接线柱相连，其中a(i)表示上端点i对应的向端点的值。如图所示：
题目要求是在给定的连线中，选取不相交连线的最大子集，即不相交连线的最大数目。并把最大不相交子集的情况给列举处理啊。
解题思路：
首先用a[i]数组表示与上面对应点相连线的下面的点，再用set[i][j]表示上面节点i与下面节点j连线的左边（包括i j连线）的最大不相交连线的个数。
于是就有公式：
max(set[i-1][j], set[i][j-1]); j != a[i]
set(i,j) =
set[i-1][j-1] + 1; j == a[i]
然后就可以对每一个i，都对所以的j求一遍。这样就可以得出结果吗，set[n][n]即我们想要的结果。
最后通过回溯把结果输出出来。
代码实现：
#include <stdio.h>#define MAX(a,b) ((a) > (b) ? (a) : (b))void circut(int a[],int set[][11],int n);void back_track(int i,int j,int set[][11]);int main(){int a[] = {0,8,7,4,2,5,1,9,3,10,6};int set[11][11];circut(a,set,10);printf("max set: %d \n",set[10][10]);back_track(10,10,set);printf("\n");return 0;}void circut(int a[],int set[][11],int n){int i,j;for (i = 0; i < n; i++){set[i][0] = 0;set[0][i] = 0;}for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){if (a[i] != j)set[i][j] = MAX(set[i-1][j],set[i][j-1]);elseset[i][j] = set[i-1][j-1] + 1;}}}void back_track(int i,int j,int set[][11]){if (i == 0)return;if (set[i][j] == set[i-1][j])back_track(i-1,j,set);else if (set[i][j] == set[i][j-1])back_track(i,j-1,set);else{back_track(i-1,j-1,set);printf("(%d,%d) ",i,j);}}/9/27 21:11
如果觉得《动态规划--电路布线(circuit layout)》对你有帮助，请点赞、收藏，并留下你的观点哦！
