唐山网站建设技术外包,html设计软件,临沂的各类网站建设,做网站材料对于电路布线问题#xff0c;想必学过动态规划的大家都很清除。今天就来讲解一下这个动态规划经典题目。 目录 问题描述输入分析最优子结构代码 问题描述
在一块电路板的上、下2端分别有n个接线柱。根据电路设计#xff0c;要求用导 线(i,π(i))将上端接线柱与下端接线柱相…对于电路布线问题想必学过动态规划的大家都很清除。今天就来讲解一下这个动态规划经典题目。 目录 问题描述输入分析最优子结构代码 问题描述
在一块电路板的上、下2端分别有n个接线柱。根据电路设计要求用导 线(i,π(i))将上端接线柱与下端接线柱相连如图所示。其中π(i)是 {1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任 何1≤ij≤n第i条连线和第j条连线相交的充分且必要的条件是π(i)π(j)。 电路布线问题要确定将哪些连线安排在第一层上使得该层上有尽可能 多的连线。换句话说该问题要求确定导线集Nets{(i,π(i)),1≤i≤n}的最 大不相交子集。
输入
两行输入 第一行是一排接线柱的个数 第二行是上接线柱对应的下接线柱位置即下文的p(i) 对于上图输入就是 10 3 1 2 4 7 9 5 6 10 8
分析
那么什么是最大不相交子集呢。咱们来一个一个字 的 扣含义。 首先最大就是字面意思最大的最多的。 其次不相交也是字面意思就是单纯的两条线不能有交点。 最后子集的定义是如果集合A的任意一个元素都是集合B的元素那么集合A称为集合B的子集通俗点说就是在给出的导线集合里面挑选几条导线这挑选的导线组成的集合就是子集。 那么组合起来说的就是在现有的线中挑选数量最多的导线且它们还不相交
我们发现这个题好像不能从考虑最后一个步骤来推导了我们好像还真不太好找出最后一个问题是什么。那么我们就换一种思路回想以前的动态规划好像都是在数组中记录数值供以后使用的而且都是一行一行的计算子问题。那我们先定义一个数组考虑到有上下两排线那就定义二维数组吧.。 设dp[i][j]表示前i个上接线柱和前j个下接线柱组成的问题的最优解包含的导线的数量(即前i个上接线柱和前j个下接线柱组成的集合的最大不相交子集中包含的导线数)
为了方便说明再来定义一些规则 上接线柱集合1234…n 下接线柱集合p(1),p(2),p(3),p(4)…p(n) p(n)代表上层接线柱n对应的下层接线柱的编号。例如下图中上接线柱1p(1)就是3 接下来以上图为例先从第一行来看来找一下规律触发一下灵感 (第1步) i1j1 (第2步) i1j2 (第3步) i1j3 唉突然发现此时增加了一个那就来想一想是什么原因让他增加的呢。我们发现当jp(1)时他就增加了接下来继续看。 (第4步) i1j3
然后类似的一直到 j10 的时候 … …
(第10步) i1j10 发现第一行除了j3的时候增加了一个其他的jp(1)的情况并没有增加为什么会这样呢思考一下。因为我们的i是等于1的所以我们的dp[1][j]他最多只有一条线我们上接线柱只包含了一个所以他只能是小于等于一的数
这就给我们一个灵感我们可以根据i,p(i)的关系进行动态规划列出可能的情况加以分析
1.考虑当 i 1的时候 1jp(i):肯定是零 2jp(i):他也肯定是一因为这时最优解里面是空的不用考虑香蕉 相交的情况 2.考虑当 i1时 1jp(i):这时肯定还是不能包含这一条导线的因为这一条导线的下接线柱没有被包含前 j 个里面。 那么这时他就相当于dp[i-1][j]。 为什么这么说呢因为在jp(i)时这一条导线是不可能被包含在我们的最优解里面的所以就相当与这一条导线i 导线对于我们的当前的解是没有任何作用的。他就相当于是前 i -1个上接线柱和前 j 个下接线柱构成的问题的最优解。 也许此时聪明好学的你会问那为什么不是dp[i-1][j-1]呢即为什么不是前 i -1个上接线柱和前 j -1 个下接线柱构成的问题的最优解呢。 此时我们直接举一个一针见血的例子如果i-1的下接线柱是 j 呢dp[i-1][j-1]是不是就把第i-1条导线给漏掉了。 2jp(i): 这时候就说明我们可以包含这个导线注意我说的是可以包含而不是一定包含。那么包含的条件是什么呢想必你肯定已经知道了就是当这条导线与最优解里面的导线都不香蕉的时候 且 包含这个导线的最优解的个数比不包含这条导线的个数要大的时候才会包含 dp[i][j]Math.max(dp[i-1][p[i]-1]1,dp[i-1][j]) 。而相交的时候就不可以包含了dp[i][j]dp[i-1][j]。
最优子结构
1.对与i1的时候肯定是满足的因为他的子问题不就是空的集合吗。 2.对于i1的时候 1jp(i) 它的最优解所包含的导线个数是是子问题的最优解dp[i-1][j]。假设子问题的最优解不是dp[i-1][j]而是R那么Rdp[i-1][j]所以原问题的最优解应该是R这就矛盾了。 2jp(i) 的时候他的子问题是选择这一条导线dp[i-1][p[i]-1]1或则不选这一条导线dp[i][j]dp[i-1][j]这两个中的最大值。对于不选择和上面的证明是一样的。 这里证明一下选择的情况 在证明之前先了解一下子问题为什么是这个集合前i-1个上接线柱前p[i]-1个下接线柱而不是其他的集合例如前i-1个上接线柱前j个下接线柱。 我们既然选择了这一个导线就说明这个导线是不会与最优解里面的导线相交的。dp[i-1][p[i]-1]是前i-1个上接线柱前p[i]-1个下接线柱 组成的解。我们的这一条导线对应的接线柱是i和p[i]。ii-1且p[i]p[i]-1所以他是这个集合中的最后一条线。就好比上图中的前4条导线4是最后一条所以他肯定不 会与前三条相交的。 **那又为什么是j-1呢而不是其他的呢**因为上接线柱是前i-1条那么就算下接线柱不是j-1是j1那么是不是就相交了呢 差不多理解了就来证明最优子结构 如果dp[i-1][p[i]-1]不是子问题的最优最优的是R那么R1dp[i-1][p[i]-1]1,所以由子问题构成的原问题的最优解应该是R1而不是dp[i-1][p[i]-1]
代码
import java.util.Scanner;public class AD {public static void MSN(int n,int[] p,int[][] dp){for(int i1;in;i){for (int j1;jn;j){if(i1){if(jp[i]){dp[i][j]dp[i-1][j];}else {dp[i][j]1;}}else {if(jp[i]){dp[i][j]dp[i-1][j];}else {dp[i][j]Math.max(dp[i-1][p[i]-1]1,dp[i-1][j]);}}}}
}public static void main(String[] args) {Scanner scannernew Scanner(System.in);int nscanner.nextInt();int[] pnew int[n1];p[0]0;for(int i1;in;i){p[i]scanner.nextInt();}int[][] dpnew int[n1][n1];// System.out.println(dp[n][n]);MSN(n,p,dp);System.out.println(dp[n][n]);}
}
