算法java实现–动态规划–电路布线问题

算法java实现–动态规划–电路布线问题

大家好,又见面了,我是全栈君。

/*
* dianlubuxian.java
* Version 1.0.0
* Created on 2017年11月30日
* Copyright ReYo.Cn
*/
package reyo.sdk.utils.test.dy;

/**
* <B>创  建 人:</B>AdministratorReyoAut <BR>
* <B>创建时间:</B>2017年11月30日 下午4:58:56<BR>
*
* @author ReYo
* @version 1.0
*/
/**
 * 电路布线问题(动态规划)
 * @author Lican
 *
 */
public class dianlubuxian {
	public int[] c;//
	public int[][] size;//最大不想交子集
	public int[] net;

	public dianlubuxian(int[] cc) {
		this.c = cc;
		this.size = new int[cc.length][cc.length];//下标从1开始
		this.net = new int[cc.length];
	}

	public void mnset(int[] c, int[][] size) {
		int n = c.length - 1;
		for (int j = 0; j < c[1]; j++) {//i=1时,分了两种情况,分别等于0,1
			size[1][j] = 0;
		}
		for (int j = c[1]; j <= n; j++) {
			size[1][j] = 1;
		}
		for (int i = 2; i < n; i++) {//i大于1时,同样分了两种情况(当i=n时单独计算,即此方法最后一行)
			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 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;
		System.out.println("最大不相交连线分别为:");
		for (int t = m - 1; t >= 0; t--) {
			System.out.println(net[t] + "  " + c[net[t]]);
		}
		return m;
	}

	public static void main(String[] args) {
		int[] c = { 0, 8, 7, 4, 2, 5, 1, 9, 3, 10, 6 };//下标从1开始,第一个数,0不算,总共10个数
		dianlubuxian di = new dianlubuxian(c);
		di.mnset(di.c, di.size);
		int x = di.traceback(di.c, di.size, di.net);
		System.out.println("最大不相交连线数目为::" + x);
	}
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107866.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • pycharm怎么装第三方库jieba_pycharm找不到第三方库

    pycharm怎么装第三方库jieba_pycharm找不到第三方库第一种想要安装什么库,就直接cmd打开pipinstall库,这种方法可以的,不过速度会有点慢不过,有时候失败就难受。第二种直接在pycharm中安装如图,不过安装失败的情况比较多(可能是我电脑问题)第三种下载了Anaconda的小伙伴,虽然conda里面含有很多库了,但是还有需要下载的就可以直接打开AnacondaNavigator,在里面进行操作,如图四、上面三种都不行有安装Anaconda的话,直接上网搜索库名加pypi..

  • stc12c5a60s2功能说明(STC12C5A60S2默认触发)

    最近学习一下SD卡的驱动,网上程序的版本很多,使用的MCU和SD卡的型号千奇百怪,学起来反而没有方向,感觉上乱七八糟的,直到现在,才直到我们平常说的SD卡实际上有很多中类别。0到2G的SD卡,最普通的卡;2G到32G的SDHC卡,也就是现在最常用的大容量SD卡;还有我没有见过的SDXC卡,容量好像在32G以上。同时还有手机上的TF卡,实际上也是SD卡只不过做工不同而已,MMC卡。学习的时候走了很

  • java面试问题大全及答案大全word,逆袭面经分享

    java面试问题大全及答案大全word,逆袭面经分享一、对象的实例化1.创建对象的方式new:最常见的方式(本质是构造器)变形1:Xxx的静态方法变形2:XxBuilder/XxoxFactory的静态方法Class的newInstance():反射的方式,只能调用空参的构造器,权限必须是publicConstructor的newInstance(Xxx):反射的方式,位于java.lang.reflect.Constructor可以调用空参、带参的构造器,权限没有要求使用clone():不调用任何构造器,当前类需

  • 13.1.2 拷贝赋值运算符、析构函数、三/五法则、阻止拷贝

    13.1.2 拷贝赋值运算符、析构函数、三/五法则、阻止拷贝

  • Django(76)isort工具对import导入进行排序「建议收藏」

    Django(76)isort工具对import导入进行排序「建议收藏」前言我们在开发项目时经常会进行导包有import*格式的,还有from*import*格式的,最后就会显示的很乱,那么有没有什么工具能对导包进行一键排序呢?答案是有的,使用isort工具i

  • 电压电流转换检测「建议收藏」

    电压电流转换检测「建议收藏」电流可以转换成电压,电压也可以转换成电流。图十就是这样一个电路。上图的负反馈没有通过电阻直接反馈,而是串联了三极管Q1的发射结,大家可不要以为是一个比较器就是了。只要是放大电路,虚短虚断的规律仍然是符合的!由虚断知,运放输入端没有电流流过,则(Vi–V1)/R2=(V1–V4)/R6……a同理(V3–V2)/R5=V2/R4……b由虚短知V1=V2……c如果R2=R6,R4=R5,则…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号