电路布线问题动态规划详解(做题思路)

对于电路布线问题,想必学过动态规划的大家都很清除。今天就来讲解一下这个动态规划经典题目。

目录

    • 问题描述
    • 输入
    • 分析
    • 最优子结构
    • 代码

问题描述

在一块电路板的上、下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}的最 大不相交子集。
在这里插入图片描述

输入

两行输入
第一行是一排接线柱的个数
第二行是上接线柱对应的下接线柱位置,即下文的p(i)
对于上图输入就是
10
3 1 2 4 7 9 5 6 10 8

分析

那么什么是最大不相交子集呢。咱们来一个一个字 的 扣含义。
首先最大就是字面意思最大的,最多的。
其次不相交也是字面意思,就是单纯的两条线不能有交点。
最后子集的定义是如果集合A的任意一个元素都是集合B的元素,那么集合A称为集合B的子集(通俗点说就是在给出的导线集合里面,挑选几条导线,这挑选的导线组成的集合就是子集)。
那么组合起来说的就是,在现有的线中挑选数量最多的导线且它们还不相交

我们发现这个题,好像不能从考虑最后一个步骤来推导了,我们好像还真不太好找出最后一个问题是什么。那么我们就换一种思路,回想以前的动态规划好像都是在数组中记录数值,供以后使用的而且都是一行一行的计算子问题。那我们先定义一个数组,考虑到有上下两排线,那就定义二维数组吧.。
设dp[i][j]表示前i个上接线柱和前j个下接线柱组成的问题的最优解包含的导线的数量(即前i个上接线柱和前j个下接线柱组成的集合的最大不相交子集中包含的导线数)

为了方便说明再来定义一些规则
上接线柱集合(1,2,3,4…n)
下接线柱集合(p(1),p(2),p(3),p(4)…p(n))
p(n)代表上层接线柱n对应的下层接线柱的编号。例如下图中上接线柱1,p(1)就是3

在这里插入图片描述

接下来以上图为例先从第一行来看,来找一下规律触发一下灵感
(第1步) i=1,j=1

在这里插入图片描述
(第2步) i=1,j=2

在这里插入图片描述
(第3步) i=1,j=3

在这里插入图片描述
唉突然发现此时,增加了一个,那就来想一想是什么原因让他增加的呢。我们发现当j>=p(1)时他就增加了,接下来继续看。
(第4步) i=1,j=3

然后类似的一直到 j==10 的时候
… …

(第10步) i=1,j=10
在这里插入图片描述
发现第一行除了j==3的时候增加了一个,其他的j>=p(1)的情况并没有增加为什么会这样呢?思考一下。因为我们的i是等于1的所以我们的dp[1][j]他最多只有一条线,我们上接线柱只包含了一个,所以他只能是小于等于一的数

这就给我们一个灵感我们可以根据i,p(i)的关系进行动态规划列出可能的情况加以分析

1.考虑当 i =1的时候
(1)j<p(i):肯定是零
(2)j>=p(i):他也肯定是一,因为这时最优解里面是空的,不用考虑香蕉🍌 (相交)的情况
2.考虑当 i>1时
(1)j<p(i):这时肯定还是不能包含这一条导线的,因为这一条导线的下接线柱没有被包含前 j 个里面。
那么这时他就相当于dp[i-1][j]。 为什么这么说呢?因为在j<p(i)时这一条导线是不可能被包含在我们的最优解里面的,所以就相当与这一条导线(i 导线)对于我们的当前的解是没有任何作用的。他就相当于是前 i -1个上接线柱和前 j 个下接线柱构成的问题的最优解。
也许此时聪明好学的你会问那为什么不是dp[i-1][j-1]呢?(即为什么不是前 i -1个上接线柱和前 j -1 个下接线柱构成的问题的最优解呢?。)
此时我们直接举一个一针见血的例子,如果i-1的下接线柱是 j 呢?dp[i-1][j-1]是不是就把第i-1条导线给漏掉了。
(2)j>=p(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.对与i<1的时候肯定是满足的,因为他的子问题不就是空的集合吗。
2.对于i>1的时候
(1)j<p(i) 它的最优解所包含的导线个数是是子问题的最优解dp[i-1][j]。假设子问题的最优解不是dp[i-1][j]而是R那么R>dp[i-1][j]所以原问题的最优解应该是R,这就矛盾了。
(2)j>=p(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]。i>i-1且p[i]>p[i]-1所以他是这个集合中的最后一条线。就好比上图中的前4条导线,4是最后一条所以他肯定不
会与前三条相交的。

在这里插入图片描述

差不多理解了,就来证明最优子结构:
如果dp[i-1][p[i]-1]不是子问题的最优,最优的是R那么R+1>dp[i-1][p[i]-1]+1,所以由子问题构成的原问题的最优解应该是R+1而不是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 i=1;i<=n;i++){for (int j=1;j<=n;j++){if(i<=1){if(j<p[i]){dp[i][j]=dp[i-1][j];}else {dp[i][j]=1;}}else {if(j<p[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 scanner=new Scanner(System.in);int n=scanner.nextInt();int[] p=new int[n+1];p[0]=0;for(int i=1;i<=n;i++){p[i]=scanner.nextInt();}int[][] dp=new int[n+1][n+1];//        System.out.println(dp[n][n]);MSN(n,p,dp);System.out.println(dp[n][n]);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/186391.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

通配符匹配

题目链接 通配符匹配 题目描述 注意点 s 仅由小写英文字母组成p 仅由小写英文字母、‘?’ 或 ‘*’ 组成‘?’ 可以匹配任何单个字符‘*’ 可以匹配任意字符序列&#xff08;包括空字符序列&#xff09; 解答思路 最初想到的是dfs 剪枝&#xff0c;但是用例超时了参照题…

搜索引擎Elasticsearch基础与实践

倒排索引 将文档中的内容分词&#xff0c;然后形成词条。记录每条词条与数据的唯一表示如id的对应关系&#xff0c;形成的产物就是倒排索引&#xff0c;如下图&#xff1a; ElasticSearch数据的存储和搜索原理 这里的索引库相当于mysql中的database。一个文档&#xff08;do…

SAP ABAP基础语法-Excel上传(十)

EXCEL BDS模板上传及赋值 上传模板事务代码&#xff1a;OAER l 功能代码&#xff1a;向EXCEL模板中写入数据示例代码如下 REPORT ZEXCEL_DOI. “doi type pools TYPE-POOLS: soi. *SAP Desktop Office Integration Interfaces DATA: container TYPE REF TO cl_gui_custom_c…

OpenGL_Learn08(坐标系统与3D空间)

目录 1. 概述 2. 局部空间 3. 世界空间 4. 观察空间 5. 剪裁空间 6. 初入3D 7. 3D旋转 8. 多个正方体 9. 观察视角 1. 概述 OpenGL希望在每次顶点着色器运行后&#xff0c;我们可见的所有顶点都为标准化设备坐标(Normalized Device Coordinate, NDC)。也就是说&#x…

uniapp使用vue

uniapp集成了Vuex&#xff0c;&#xff0c;并不需要安装vuex 定义自己的vuex vuex中独立命名空间&#xff1a; 可以在模块中使用 namespaced 属性&#xff0c;设置为 true&#xff0c;&#xff0c;这样做的好处是&#xff0c;&#xff0c;不同模块之间的state&#xff0c;mut…

istio 学习笔记

参考&#xff1a;istio简介和基础组件原理&#xff08;服务网格Service Mesh&#xff09;-CSDN博客 Istio 微服务框架 服务治理。 Istio的关键功能: HTTP/1.1&#xff0c;HTTP/2&#xff0c;gRPC和TCP流量的自动区域感知负载平衡和故障切换。 通过丰富的路由规则&#xf…

12 # 手写 findIndex 方法

findIndex 的使用 findIndex() 方法返回数组中满足提供的测试函数的第一个元素的索引。若没有找到对应元素则返回 -1。 <script>var arr [1, 3, 5, 7, 8];var result arr.findIndex(function (ele, index, array) {console.log("ele----->", ele);conso…

C#中.NET 7.0控制台应用使用LINQtoSQL、LINQtoXML

目录 一、新建控制台应用和数据库连接 二、手动添加System.Data.Linq程序包 三、手动添加System.Data.SqlClient程序包 四、再次操作DataClasses1.dbml 五、示例 1.源码 2.xml文件 默认安装的.NET 7.0控制台应用是不支持使用LINQtoSQL、LINQtoXML的。 默认安装的.NET F…

如何用Java高效地存入一万条数据?这可能是你面试成功的关键!

大家好&#xff0c;我是你们的小米&#xff0c;一个热爱技术、喜欢分享的29岁程序猿。今天我要和大家聊一聊一个常见的面试题&#xff1a;在Java中&#xff0c;当我们需要将一万条数据存储到数据库时&#xff0c;如何能够提高存储效率呢&#xff1f; 在面试过程中&#xff0c;…

设计模式(3)-结构型模式

结构型模式 结构型模式描述如何将类或对象按某种布局组成更大的结构。它分为类结构型模式和对象结构型模式&#xff0c;前者采用继承机制来组织接口和类&#xff0c;后者釆用组合或聚合来组合对象。 由于组合关系或聚合关系比继承关系耦合度低&#xff0c;满足“合成复用原则…

【机器学习】梯度下降预测波士顿房价

文章目录 前言一、数据集介绍二、预测房价代码1.引入库2.数据3.梯度下降 总结 前言 梯度下降算法学习。 一、数据集介绍 波士顿房价数据集&#xff1a;波士顿房价数据集&#xff0c;用于线性回归预测 二、预测房价代码 1.引入库 from sklearn.linear_model import Linear…

Python爬虫实战-批量爬取美女图片网下载图片

大家好&#xff0c;我是python222小锋老师。 近日锋哥又卷了一波Python实战课程-批量爬取美女图片网下载图片&#xff0c;主要是巩固下Python爬虫基础 视频版教程&#xff1a; Python爬虫实战-批量爬取美女图片网下载图片 视频教程_哔哩哔哩_bilibiliPython爬虫实战-批量爬取…

【Java】I/O流—缓冲流的基础入门和文件拷贝的实战应用

&#x1f33a;个人主页&#xff1a;Dawn黎明开始 &#x1f380;系列专栏&#xff1a;Java ⭐每日一句&#xff1a;你能坚持到什么程度&#xff0c;决定你能达到什么高度 &#x1f4e2;欢迎大家关注&#x1f50d;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; 文章目录 一.&…

RapidSSL证书

RapidSSL是一家经验丰富的证书颁发机构&#xff0c;主要专注于提供标准和通配符SSL证书的域验证SSL证书。在2017年被DigicertCA收购后&#xff0c;RapidSSL改进了技术并开始使用现代基础设施。专注于为小型企业和网站提供基本安全解决方案的SSL加密。RapidSSL它具有强大的浏览器…

ZYNQ_project:key_led

条件里是十进制可以不加进制说明&#xff0c;编译器默认是10进制&#xff0c;其他进制要说明。 实验目标&#xff1a; 模块框图&#xff1a; 时序图&#xff1a; 代码&#xff1a; include "para.v"module key_filter (input wire …

python3.8.10虚拟环境安装talib总报平台不匹配

目录 环境&#xff1a; 需求&#xff1a; 问题&#xff1a; 概述 过程及解决 解决方案总结 环境&#xff1a; 操作系统&#xff1a;window10、64位 开发工具&#xff1a;pycharm python版本&#xff1a;python3.8.10 需求&#xff1a; 在python3.8.10的虚拟环境中安…

短短 45 分钟发布会,OpenAI 如何再次让 AI 圈一夜未眠

目录 前言 1. GPT-4 Turbo&#xff0c;更快&#xff0c;更省钱 2. GPT Store 来了&#xff01; 3. 零代码创建 AI Agent 前言 对于 AI 行业从业者来说&#xff0c;刚刚可能是一夜未眠。 北京时间 11 月 7 日凌晨&#xff0c;美国人工智能公司 OpenAI 的开发者大会正式开…

HTTParty库数据抓取代码示例

使用HTTParty库的网络爬虫程序&#xff0c; ruby require httparty # 设置服务器 proxy_host proxy_port # 使用HTTParty库发送HTTP请求获取网页内容 response HTTParty.get(/, :proxy > { :host > proxy_host, :port > proxy_port }) # 打印获取的网页内容 …

亚马逊云科技产品测评』活动征文|通过使用Amazon Neptune来预测电影类型初体验

文章目录 福利来袭Amazon Neptune什么是图数据库为什么要使用图数据库什么是Amazon NeptuneNeptune 的特点 快速入门环境搭建notebook 图神经网络快速构建加载数据配置端点Gremlin 查询清理 删除环境S3 存储桶删除 授权声明&#xff1a;本篇文章授权活动官方亚马逊云科技文章转…

Sketch是什么软件,如何收费和获得免费版

Sketch软件为设计师构建了一个优秀的本地Mac应用程序。Sketch是整个设计过程的平台&#xff0c;通过基于Web的工具共享工作&#xff0c;获取反馈&#xff0c;测试原型&#xff0c;并将其移交给任何浏览器。Sketch软件的定价根据不同的许可类型和订阅计划而变化。本文从Sketch软…