mnset.java

《算法设计与分析》王晓东编著

public class MNset {
	public static void mnset(int []c, int [][]size)
	{
		int n=c.length-1;
		for (int j=0;j<c[1];j++)
			size[1][j]=0;
		for (int j=c[1];j<=n;j++)
			size[1][j]=1;
		for (int i=2;i<n;i++) {
			for (int j=0;j<c[i];j++)
				size[i][j]=size[i-1][j];
			for (int j=c[i];j<=n;j++)
				size[i][j]=Math.max(size[i-1][j],size[i-1][c[i]-1]+1);
		}
		size[n][n]=Math.max(size[n-1][n],size[n-1][c[n]-1]+1);			
	}

	public static int traceback(int []c, int [][]size, int []net)
	{
		int n=c.length-1;
		int j=n;
		int m=0;
		for (int i=n;i>1;i--)
			if (size[i][j]!=size[i-1][j]) {
				net[m++]=i;
				j=c[i]-1;
			}
		if (j>=c[1])
			net[m++]=1;
		return m;
	}
	
	public static void main(String[] args) {
		/* 初始化电路布线(i,π(i)):
		 * (1,8),(2,7),(3,4),(4,2),(5,5),
		 * (6,1),(7,9),(8,3),(9,10),(10,6) */
		int[] c=new int[]{0,8,7,4,2,5,1,9,3,10,6};
		
		int[][] size=new int[c.length][c.length];
		int[] net=new int[c.length];
		
		/* 计算最大的连线数 */
		mnset(c,size);
		
		/* 生成一组最优方案 */
		int max=traceback(c,size,net);
		
		/* 输出结果 */
		System.out.println("Max="+max);
		for (int i=0;i<max;i++)
			System.out.println("("+net[i]+","+c[net[i]]+")");
	}
}