贪心算法学习五

例题一

解法(贪⼼):
贪⼼策略:
我们的任何选择,应该让这个数尽可能快的变成 1
对于偶数:只能执⾏除 2 操作,没有什么分析的;
对于奇数:
i. n== 1 的时候,不⽤执⾏任何操作;
ii. n == 3 的时候,变成 1 的最优操作数是 2
iii. (n / 2) % 2 == 0 的时候,那么它的⼆进制表⽰是 ......01 ,最优的⽅式应该选择 -1 ,这样就可以把末尾的 1 ⼲掉,接下来执⾏除法操作,能够更快的变成 1 ;
iv. (n / 2) % 2 == 1 的时候,那么它的⼆进制表⽰是 ......11 ,此时最优的策略应该是 +1 ,这样可以把⼀堆连续的 1 转换成 0 ,更快的变成 1

例题二

解法⼀(动态规划):
将数组按照左端点排序之后,问题就转化成了最⻓上升⼦序列模型,那接下来我们就可以⽤解决最⻓上升⼦序列的经验,来解决这个问题。
1. 状态表⽰:
dp[i] 表⽰:以 i 位置的箱子为结尾的堆起来的箱子序列中,最高的箱子序列的高度;
2. 状态转移⽅程:
dp[i] = max(dp[i] , dp[j] + box[i] ) 其中 0 <= j < i && box[i][0] > box[j][0] && box[i][1] > box[j][1]&& box[i][2] > box[j][2] ;
3. 初始化:
初始化为 每个箱子原来的高度  
4. 填表顺序:
从左往右;
5. 返回值:
整个 dp 表中的最⼤值。

例题三

解法⼀(动态规划):
将数组按照左端点排序之后,问题就转化成了最⻓上升⼦序列模型,那接下来我们就可以⽤解决最⻓上升⼦序列的经验,来解决这个问题(虽然会超时,但是还是要好好写代码)。
1. 状态表⽰:
dp[i] 表⽰:以 i 位置的信封为结尾的所有套娃序列中,最⻓的套娃序列的⻓度;
2. 状态转移⽅程:
dp[i] = max(dp[j] + 1) 其中 0 <= j < i && e[i][0] > e[j][0] && e[i][1] > e[j][1] ;
3. 初始化:
全部初始化为 1
4. 填表顺序:
从左往右;
5. 返回值:
整个 dp 表中的最⼤值。
解法⼆(重写排序 + 贪⼼ + ⼆分):
当我们把整个信封按照「下⾯的规则」排序之后:
i. 左端点不同的时候:按照「左端点从⼩到⼤」排序;
ii. 左端点相同的时候:按照「右端点从⼤到⼩」排序;
我们发现,问题就变成了仅考虑信封的「右端点」,完完全全的变成的「最⻓上升⼦序列」的模型。那么我们就可以⽤「贪⼼ + ⼆分」优化我们的算法。

例题四

解法⼀(动态规划):
1. 状态表⽰:
dp[0][i]:表示取到第 i 个数的时候%3余数为0的最大值;
dp[1][i]:表示取到第 i 个数的时候%3余数为1的最大值;
dp[2][i]:表示取到第 i 个数的时候%3余数为2的最大值。
2. 状态转移⽅程:
1.当nums[i-1] % 3 == 0时
dp[0][i] = max(dp[0][i - 1], dp[0][i - 1] + nums[i - 1]);
dp[1][i] = max(dp[1][i - 1], dp[1][i - 1] + nums[i - 1]);
dp[2][i] = max(dp[2][i - 1], dp[2][i - 1] + nums[i - 1]);

2.当nums[i - 1] % 3 == 1时

dp[0][i] = max(dp[0][i - 1], dp[2][i - 1] + nums[i - 1]);
dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + nums[i - 1]);
dp[2][i] = max(dp[2][i - 1], dp[1][i - 1] + nums[i - 1]);

3.当nums[i - 1] % 3 == 2时

dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] + nums[i - 1]);
dp[1][i] = max(dp[1][i - 1], dp[2][i - 1] + nums[i - 1]);
dp[2][i] = max(dp[2][i - 1], dp[0][i - 1] + nums[i - 1]);

3. 初始化:
dp[0][0] = 0, dp[1][0] = INT_MIN, dp[2][0] = INT_MIN;
4. 填表顺序:
从左往右;
5. 返回值:
dp[ 0 ][ n ]
解法二(正难则反 + 贪⼼ + 分类讨论):
正难则反:
我们可以先把所有的数累加在⼀起,然后根据累加和的结果,贪⼼的删除⼀些数。
分类讨论:
设累加和为 sum ,⽤ x 标记 %3 == 1 的数,⽤ y 标记 % 3 == 2 的数。那么根据 sum 的余数,可以分为下⾯三种情况:
a. sum % 3 == 0 ,此时所有元素的和就是满⾜要求的,那么我们⼀个也不⽤删除;
b. sum % 3 == 1 ,此时数组中要么存在⼀个 x ,要么存在两个 y 。因为我们要的是最⼤值,所以应该选择 x 中最⼩的那么数,记为 x1 ,或者是 y 中最⼩以及次⼩的两个数,记为y1,y2 。 那么,我们应该选择两种情况下的最⼤值: max(sum - x1, sum - y1 - y2)
c. sum % 3 == 2 ,此时数组中要么存在⼀个 y ,要么存在两个 x 。因为我们要的是最⼤值,所以应该选择 y 中最⼩的那么数,记为 y1 ,或者是 x 中最⼩以及次⼩的两个数,记为 x1, x2
那么,我们应该选择两种情况下的最⼤值: max(sum - y1, sum - x1 - x2)

例题五

解法(贪⼼):
贪⼼策略:
每次处理⼀批相同的数字,往 n 个空⾥⾯摆放;每次摆放的时候,隔⼀个格⼦摆放⼀个数;优先处理出现次数最多的那个数。

例题六

解法(贪⼼):
贪⼼策略:
与上⾯的⼀道题解法⼀致~

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

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

相关文章

如何使用ios自带语音转文字工具?

ios自带语音转文字是iOS系统中自带的语音转文字功能主要应用于以下几个方面&#xff1a; 1. 语音输入&#xff1a;在iOS的任何文本输入框中&#xff0c;通常都有一个麦克风图标&#xff0c;点击后可以进行语音输入&#xff0c;系统会将你的语音实时转换成文字。 2. Siri&…

1. NAS和SAN存储

NAS和SAN存储 一、存储设备1、根据工作方式2、DAS 直接附加存储3、NAS存储4、SAN存储 二、模拟配置SAN存储1、创建虚拟机、安装openfiler2、访问openfiler webUI3、创建RAID设备4、开启iSCSI服务5、配置SAN存储设备共享空间5.1 设置IQN 6、业务服务器连接使用存储6.1 安装客户端…

JDK17 你的下一个白月光

JDK版本升级的非常快&#xff0c;现在已经到JDK20了。JDK版本虽多&#xff0c;但应用最广泛的还得是JDK8&#xff0c;正所谓“他发任他发&#xff0c;我用Java8”。 但实际情况却不是这样&#xff0c;越来越多的java工程师拥抱 JDK17&#xff0c;于是了解了一下 JDK17新语法&a…

C#开发-集合使用和技巧(二)Lambda 表达式介绍和应用

C#开发-集合使用和技巧 Lambda 表达式介绍和应用 C#开发-集合使用和技巧介绍简单的示例&#xff1a;集合查询示例&#xff1a; 1. 基本语法从主体语句上区分&#xff1a;1. 主体为单一表达式2. 主体是代码块&#xff08;多个表达式语句&#xff09; 从参数上区分1. 带输入参数的…

69. UE5 RPG 使用Gameplay Cue 实现技能表现效果

在上一章中&#xff0c;我们实现了敌人的攻击技能的特效和音效。如果我们在多人模式下打开&#xff0c;发现&#xff0c;其它客户端看不到对应的效果。 造成这种问题的原因是因为敌人的技能是运行在服务器端的&#xff0c;它只复制到拥有它的客户端&#xff0c;而敌人的效果对于…

仿FC数学金刚游戏介绍

简介 Math Monkey是Simple2l工作室开发的第二款小游戏&#xff0c;灵感来源于FC游戏平台的数学金刚游戏。小学时玩FC游戏是业余时间最期待的事情&#xff0c;还记得有一次和玩伴玩游戏时已经晚上了&#xff0c;于是约定再玩一把就各回各家&#xff0c;没想到又连玩了N把每一把…

Postman下发流表至Opendaylight

目录 任务目的 任务内容 实验原理 实验环境 实验过程 1、打开ODL控制器 2、网页端打开ODL控制页面 3、创建拓扑 4、Postman中查看交换机的信息 5、L2层流表下发 6、L3层流表下发 7、L4层流表下发 任务目的 1、掌握OpenFlow流表相关知识&#xff0c;理解SDN网络中L…

Jira,一个强大灵活的项目和任务管理工具 Python 库

目录 01初识 Jira 为什么选择 Jira? 02安装与配置 安装 jira 库 配置 Jira 访问 获取 API token: 配置 Python 环境: 03基本操作 创建项目 创建任务 查询任务 更新任务 删除任务 04高级操作 处理子任务 搜索任务 添加附件 评论任务 05实战案例 自动化创建…

001 Spring介绍

文章目录 特点1.方便解耦&#xff0c;简化开发2.AOP编程的支持3.声明式事务的支持4.方便程序的测试5.方便集成各种优秀框架6.降低Java EE API的使用难度7.Java源码是经典学习范例 好处什么是耦合和内聚耦合性&#xff0c;也叫耦合度&#xff0c;是对模块间关联程度的度量内聚标…

react-day1

1.react是什么呢&#xff1f; react是由Meta公司开发&#xff0c;是一个用于构建web和原生交互界面的库 2.react 项目修改文件保存后 &#xff0c;不能实时更新&#xff0c;需要&#xff1a; 在和package.json文件同目录的地方&#xff0c;新建.env文件&#xff1a;里面加入…

MySQL数据操作与查询- 连接查询

一、引入 1、为什么需要使用连接查询&#xff1f; 查询信息的来源如果来自多张表&#xff0c;则必须对这些表进行连接查询。 2、连接查询的分类 内连接和外连接。 二、内连接 1、概述 将两张表的记录组合在一起&#xff0c;产生一个新的结果。 &#xff08;1&#xff09…

C++初学者指南第一步---2. Hello world

C初学者指南第一步—2. Hello world 目录 C初学者指南第一步---2. Hello world1.源文件 “Hello.cpp”2.编译hello.cpp3.术语4.编译器标志5.不要使用 “using namespace std;” &#xff01; 1.源文件 “Hello.cpp” #include <iostream> // our first program int main…

SqlSugar使用DbFirst对象根据数据库表结构创建实体类-C#

本文所述开发环境&#xff1a;.C#、NET8、Visual Studio2022 1. 在项目中安装SqlSugar 在Visual Studio2022中新建一个 C# 的控制台应用程序&#xff0c;框架选择 .Net8。新建后如下图所示&#xff1a; 然后打开NuGet程序包管理器 搜索 SqlSugarCore 并安装 安装后在解决方案…

【Linux】 进程信号的发生

送给大家一句话&#xff1a; 何必向不值得的人证明什么&#xff0c;生活得更好&#xff0c;乃是为你自己。 -- 亦舒 进程信号的发生 1 何为信号2 信号概念的基础储备3 信号产生kill系统调用alarm系统调用异常core term Thanks♪(&#xff65;ω&#xff65;)&#xff89;谢谢…

会声会影色彩校正在哪里 会声会影色彩素材栏在哪 会声会影中文免费版下载

会声会影是一款功能强大的视频编辑软件&#xff0c;它可以帮助用户轻松地编辑和制作视频。在进行视频编辑时&#xff0c;色彩校正是一个重要的步骤&#xff0c;它可以调整视频的色调、亮度和对比度等参数&#xff0c;使视频更加生动和鲜明。在会声会影中&#xff0c;色彩校正功…

linux 部署瑞数6实战(维普,药监局)第一部分

声明 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01;wx 本文章未经许可禁止转载&…

深入浅出談 隐马尔可夫的概念(2/ 2)-- 训练理论

文章目录 一、说明二、HMM 三大问题三、评估问题——前向-后向算法四、.解码问题——维特比算法五、学习问题——EM算法六、 连续隐马尔可夫 一、说明 在许多机器学习的章节中&#xff0c;常常遇见 HMM &#xff0c;往往看到它的数学式子后&#xff0c;就当没看到似的跳过去了…

【Python网络爬虫分步走】使用LXML解析网页数据

Python网络爬虫分步走 – 使用LXML解析网页数据 Web Scraping in Python - Using LXML to Parse Web Data By Jackson@ML Lxml作为Python的第三方库,提供易用的且功能强大的API,用来解析XML和HTML文档。事件驱动的API被用于分步骤解析。 本文简要介绍使用lxml库解析网页的基…

UML与设计模式

1、关联关系 关联关系用于描述不同类的对象之间的结构关系&#xff0c;它在一段时间内将多个类的实例连接在一起。关联关系是一种静态关系&#xff0c;通常与运行状态无关&#xff0c;而是由“常识”、“规则”、“法律”等因素决定的&#xff0c;因此关联关系是一种强关联的关…

北斗三代一体式数传终端短报文

北斗三代一体式数传终端短报文M20C-V30针对船载通信和导航应用推出的一款支持北斗 RDSS/RNSS 功能的船载一体机。北斗数传终端内部集成了北斗多频天线、射频、基带以及主控等功能单元&#xff0c;可实现 RDSS 定位、短报文通信和 RNSS 导航定位等功能。M20C-V30型北斗数传终端体…