贪心算法 - 学习笔记 【C++】
2024-12-09 - 第 38 篇
贪心算法 - 学习笔记
作者(Author): 郑龙浩 / 仟濹(CSND账号名)
贪心算法
学习课程:
https://www.bilibili.com/video/BV1f84y1i7mv/?spm_id_from=333.337.search-card.all.click&vd_source=2683707f584c21c57616cc6ce8454e2b
一、基本概念
贪心算法是一种在每个步骤都选择当前最优决策的算法。它只考虑当下的最好情况,希望通过这些局部最优选择来得到全局最优解。 特点是简单高效、具有无后效性。不过它不是万能的,有些情况不能通过它得到全局最优解,但在像哈夫曼编码这类有最优子结构的问题中很有效。
可以分为这四步( AI 生成 )
- 分解问题:将一个复杂的大问题分解为一系列的子问题。例如在活动安排问题中,把安排所有活动这个大问题,分解为一个个单独活动的选择。
- 确定贪心策略:找到一个合适的贪心策略,即确定在每个子问题中怎样选择才是局部最优。比如在找零问题中,贪心策略是优先使用面值大的硬币。
- 按照策略进行选择:依据确定好的贪心策略,在每个子问题里做出选择。以活动安排为例,就按照结束时间最早这个策略来选择活动。
- 合并结果:将所有子问题的局部最优解合并起来,得到最终的解。不过要注意这个解不一定是全局最优解。
简单一点讲就是:
- 无论能否吞得下,能吞一点。
- 根据当前的情况做出当前情况的最佳选择。
- 当做出选择的时候,要永不改变。反之,回溯算法可以“反悔”。
- 循环下去,使用“局部最优解”,逐步得到“整体最优解”
二、入门案例
海盗打劫商船,商船上装满古董,每件古董的重量不同,但每件古董的价值都相同,海盗船有最大载重的限制。
- 假设 最大载重 500
问,最多装几件古董,既不翻船又获利最大?
思路:
// 思路: // 1. 先排序,从小到大 --> 目的就是从最轻的算起,逐步往重的方放,直到放到放不下为止 // 2. 从 0 开始,逐步累加,直到累加和大于 500 为止 --> 意思就是,边放边计算数量,直到船上放不开。 // 先累加,然后判断累加后的是否 > 最大载重// 若 > 最大载重,就退出循环// 若 < 最大载重,就继续累加
#include <iostream>
#include <algorithm>
using namespace std;
int main( void ){int data[] = { 8, 20, 5, 80, 3, 420, 14, 330, 70 };int max = 500, ans = 0, sum = 0; // 最大载重, 古董数量, 总重量int cnt = sizeof( data ) / sizeof( data[ 0 ] ); // 计算数组元素个数sort( data, data + cnt ); // 排序for ( int i = 0; i < cnt; i ++ ){// 先累加,然后判断累加后的是否 > 最大载重// 若 > 最大载重,就退出循环// 若 < 最大载重,就继续累加sum += data[ i ]; // 总重量累加if( sum > max ) // 如果当前重量大于最大载重,就退出循环break;ans ++; // 古董数量累加}cout << "古董数量:" << ans << endl;return 0;
}
三、初级案例 - 字节跳动笔试题
一个很长的花坛,一部分地已经种植了花,另一部分却没有。
花不能种植在相邻的地块上,否则它们会争夺水源,两者都会死去。
给你一个整数数组表示花坛,0 表示没种植花,1 表示种植了花。
给定一个数n,能不能种下 n 朵花?
分析 + 思路:
- 首先要知道:给定了一个数组(表示的花坛),我们需要在给定的数组中种花。Eg: 10001 --> 可以种一朵花。 10010 --> 不可以种花. 10000001 / 1000001 --> 可以种两朵花
- 可以种花的条件是:当前位置的左边和右边都没有花。 Eg: 10001 --> 可以种一朵花。 10010 --> 不可以种花. 10000001 / 1000001 --> 可以种两朵花
- 最终计算的是,n朵花是否能全部种到 给定的花坛中去(数组)
- 封装一个函数,用来判断 是否可以将 n 朵花 种完
这个地方的判断需要特别注意,主要是 最两边的元素判断。
特别容易出错。- 函数过程:遍历数组,如果当前位置可以种花,则 将当前位置的元素变为 “1”,并且 种植数量 ++
- 判断 种植数量 是否等于 n ,如果等于 n ,则打印 Yes ,否则打印 No
// [字节跳动]笔试真题
// 一个很长的花坛,一部分地已经种植了花,另一部分却没有。
// 花不能种植在相邻的地块上,否则它们会争夺水源,两者都会死去。// 给你一个整数数组表示花坛,0 表示没种植花,1 表示种植了花。// **给定一个数n,能不能种下 n 朵花?** 能打印 Yes, 不能打印 No// 分析 + 思路:
// 首先要知道:给定了一个数组(表示的花坛),我们需要在给定的数组中种花。
// 可以种花的条件是:当前位置的左边和右边都没有花。 Eg: 10001 --> 可以种一朵花。 10010 --> 不可以种花. 10000001 / 1000001 --> 可以种两朵花
// 最终计算的是,n朵花是否能全部种到 给定的花坛中去(数组)// 1. 封装一个函数,用来判断 是否可以将 n 朵花 种完
// 这个地方的判断需要特别注意,主要是 最两边的元素判断。
// 特别容易出错。
// 2. 函数过程:遍历数组,如果当前位置可以种花,则 将当前位置的元素变为 “1”,并且 种植数量 ++
// 3. 判断 种植数量 是否等于 n ,如果等于 n ,则打印 Yes ,否则打印 No#include <iostream>
#include <vector>
// 判断是否可以将 n 朵花 种完
bool canPlant( bool *data, int dataSize, int n ){ // data 表示数组首地址 dataSize 表示 存储的数据的宽度 即花坛的长度, n 表示需要种植的花的数量int count = 0; // 表示 种植数量for( int i = 0; i < dataSize; i ++ ){if( data[ i ] == 0 && data[ i - 1 ] == 0 && data[ i + 1 ] == 0 && i - 1 >= 0 && i + 1 < dataSize ){ // 种植条件: 左右两边都没有花 && 边界条件:不能越界data[ i ] = 1; // 种花count ++; // 种植数量 ++}if( count >= n ) return 1; // 如果 count 种植数量 已经满足了 n 朵花,无需再进行多余的循环}return 0;
}
using namespace std;
int main( void ){bool data[] = { 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1 };int n;cin >> n; // 输入种植几朵花if ( canPlant( data, sizeof(data) / sizeof(data[0]), n ) )cout << "Yes" << endl;elsecout << "No" << endl;return 0;
}
四、中级案例 - 华为笔试题
给定一个整数数组,表示在同一行的行星。
每一个元素,其绝对值表示行星的大小,正负表示行星的移动方向
正 表示向右移动, 负 表示向左移动.
每一颗行星 速度相同。
碰撞规则
- 两个行星碰撞,较小的行星会爆炸。
- 如果大小相同,则两颗都会爆炸。
- 两颗移动方向相同的行星,永远不会发生碰撞。
分析 + 思路
分析 + 思路:
封装一个函数,用来判断 + 计算 全部星球碰撞以后留下来的行星。并存入一个新的数组。
函数过程:两个变量分别表示的 左边的行星 与 右边的行星
几种情况:(1)为相同的情况;(2)(3)为不先相同的情况
(1). 两个行星方向 【相同】,则永远不会发生碰撞
(2). 两个行星方向 【相反】 && 左边质量 > 右边质量 --> 右边行星爆炸
(3). 两个行星方向 【相反】 && 左边质量 < 右边质量 --> 左边行星爆炸
(4). 两个行星方向 【相反】 && 左边质量 == 右边质量 --> 两个行星都爆炸
注: 【情况(2)】 与 【情况(3)】【情况(4)】 合并为一种情况。
循环 + 判断 完所有的情况以后,最后将留下来的行星 【存入】 新的数组中。
将留下来的行星质量存入 传来的数组参数中。
可能会有错误。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 判断 + 计算 全部星球碰撞以后留下来的行星。并存入一个新的数组。
void newdata ( vector <int> &data, vector <int> &data2 ){// 使用 ector 就不用单独计算 数组的大小了// 参数: 原来容器, 容器大小, 新容器(存放星球爆炸以后的数据)int left = 0, right = 1; // 左边的星球 右边的星球;while( right < data.size()){ // 循环条件:右边的星球 【不超过】 星球容器宽度// 两个行星方向 【相同】,则永远不会发生碰撞if( data[left] * data[right] > 0 ){ // 方向一致,则永远不会发生碰撞【不爆炸】 【情况(1)】left = right;right ++;continue; // 没有爆炸,数据未更新,表示位置变量发生变化,重新进入循环// 注: 下面这种写法是有错误的,因为 left 并不一定 移动到 下一个星球 --> 可能会出现 bug// 只有 right 可以进行 ++// left++;// right++;} else if( data[left] * data[right] < 0 ){ // 两个行星方向 【相反】 --> 两种情况//【情况(2)】 --> 左边质量 > 右边质量 --> 右边行星爆炸if( abs(data[left]) > abs(data[right]) ){//【右边消失】data.at( right ) = 0; // 0 表示爆炸的星球left = right;right ++;continue; // 已经爆炸,数据更新,表示位置变量发生变化,重新进入循环} else if ( abs(data[left]) < abs(data[right]) )//【情况(3)】 左边质量 < 右边质量 --> 左边行星爆炸{ data.at( left ) = 0; // 0 表示爆炸的星球left = right;right ++;continue; // 已经爆炸,数据更新,表示位置变量发生变化,重新进入循环} else // 【情况(4)】左边质量 == 右边质量 --> 两个行星全都爆炸{data.at( left ) = 0; // 0 表示爆炸的星球data.at( right ) = 0; left = right;right ++;continue;}}// 判断 left 与 right 的指针位置已经爆炸if ( data[ left ] == 0 ) // 左边的星球已经爆炸{left = right;right ++;continue; // 没有爆炸,数据未更新,表示位置变量发生变化,重新进入循环}else if ( data[ right ] == 0 ){ // 右边的星球已经爆炸right ++; // 只需进行 右边位置移动即可continue;}// cout << right << endl;// cout << "123" << endl; // 测试死循环}// 将更新后的 为 "1" 的数据存入 新的容器中for( auto i = data.begin() ; i != data.end(); i++ ){if( *i!= 0 ){ // 将没爆炸的星球存入新的容器中data2.push_back( *i );}}
}
int main( void ){vector <int> data = {10, 2, -2, -2, -5}; // 随机写几个数据进行测试vector <int> data2; // 新的容器newdata ( data, data2 ); // 计算留下的星球cout << "爆炸个数:" << data.size() - data2.size() << endl; // 打印 爆炸的星球个数cout << "留下的星球:" << endl;for ( auto i = data2.begin(); i != data2.end(); i++ ){cout << *i << " "; // 打印 留下的星球}return 0;
}
相关文章:
贪心算法 - 学习笔记 【C++】
2024-12-09 - 第 38 篇 贪心算法 - 学习笔记 作者(Author): 郑龙浩 / 仟濹(CSND账号名) 贪心算法 学习课程: https://www.bilibili.com/video/BV1f84y1i7mv/?spm_id_from333.337.search-card.all.click&vd_source2683707f584c21c57616cc6ce8454e2b 一、基本…...

精确的单向延迟测量:使用普通硬件和软件
论文标题:Precise One-way Delay Measurement with Common Hardware and Software(精确的单向延迟测量:使用普通硬件和软件) 作者信息:Maciej Muehleisen 和 Mazen Abdel Latif,来自Ericsson Research Eri…...
【MySQL 进阶之路】存储引擎和SQL优化技巧分析
1.InnoDB和MyISAM存储引擎的区别是什么?你在哪些场景下选择InnoDB? Innodb是高并发,支持事务跟行级锁,myisam不支持事务和行级锁,支持表级锁,不支持高并发。innodb底层是B树,适合范围查询&#…...
vue+elementUI从B页面回到A页面并且定位到A页面的el-tabs的某个页签
场景 做项目碰到一个需求,不能使用组件缓存keep-alive,但是需要跳转到B页面后,点击B页面的返回回到A页面的某个页签,灵机一动利用路由拦截去判断即将要跳转的页面后,在获取vm里对应的标签变量进行赋值,实现…...

{结对编程/大模型} 实践营项目案例 | 基于RAG搭建政策问答智能聊天助手
在构建政策问答智能聊天助手的过程中,我们采用了 RAG(Retrieval-Augmented Generation)技术。RAG 是一种结合了检索和生成的混合型自然语言处理技术,它通过检索相关信息来增强生成模型的上下文理解能力。RAG 的主要优点在于能够有…...

【Canvas与图标】乡土风金属铝边立方红黄底黑字图像处理图标
【成图】 120*120图标: 大小图: 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>金属铝边立方红黄底黑…...

【开源】A064—基于JAVA的民族婚纱预定系统的设计与实现
🙊作者简介:在校研究生,拥有计算机专业的研究生开发团队,分享技术代码帮助学生学习,独立完成自己的网站项目。 代码可以查看项目链接获取⬇️,记得注明来意哦~🌹 赠送计算机毕业设计600个选题ex…...

C++实现一个经典计算器(逆波兰算法)附源码
1、本篇要实现的内容 最近,大家讨论计算器的实现比较热,今天我也来用C和Visual Studio实现一个计算器的小程序。这里使用逆波兰算法,能够根据当前用户输入的算式表达式字符串,计算出所要的结果,算式字符串可以包括加、…...
Python知识分享第二十二天-数据结构入门
数据结构 “”" 基础概念: 程序 数据结构 算法 数据结构 存储和组织数据的方式. 算法 解决问题的思维, 思路, 方式. 算法的特性:独立性: 算法 思维, 是解决问题的思路和方式, 不依赖语言.5大特性: 有输入, 有输出, 有穷性, 确定性, 可行性.问: 如何衡量算法的优劣?…...

【WRF理论第十三期】详细介绍 Registry 的作用、结构和内容
目录 1. Introduction:介绍 Registry 的作用和功能。2. Registry Contents:详细描述 Registry 的结构和内容,包括各个部分的条目类型。2.1. DIMSPEC ENTRIES(维度规格条目)2.2. STATE ENTRIES(状态变量条目…...
Android启动优化指南
文章目录 前言一、启动分类与优化目标1、冷启动1.1 优化思路1.2 延迟初始化与按需加载1.3 并行加载与异步执行1.4 资源优化与懒加载1.5 内存优化与垃圾回收控制 2. 温启动2.1 优化应用的生命周期管理2.2 数据缓存与懒加载2.3 延迟渲染与视图优化 3. 热启动3.1 保持应用的状态3.…...
【ETCD】【源码阅读】configureClientListeners () 函数解析
逐步解析 configureClientListeners 函数 configureClientListeners 是 ETCD 的一个重要函数,用于配置客户端通信的监听器(Client Listeners)。这些监听器主要负责处理外部客户端与 ETCD 服务之间的通信,包括 HTTP 和 gRPC 请求。…...

IO进程学习笔记
man手册 普通命令。系统调用的函数。库函数。特殊文件。文件格式。游戏。附加的一些变量 IO介绍 I:input 输入 O:output 输出 对文件的输入和输出 输入-》写文件,将文件中的内容写到内存中去 输出-》读文件,将内存中的内容读取到文…...
智能手机回暖:华为点火,小米荣耀OV拱火
进入11月中下旬,智能手机圈再度热闹起来。包括华为、小米、OPPO、vivo等诸多手机厂商,都在陆续预热发布新机,其中就包括华为Mate 70、小米Redmi K80、vivo的S20,IQOO Neo10等热门新机,这些热门新机的集中上市迅速吸引了…...

Sqoop导入数据(mysql---->>hive)
目录 数据传输流程脚本报错和异常说明1. Caused by: java.lang.ClassNotFoundException: org.apache.hadoop.hive.conf.HiveConf2. 数据导入hive后显示NULL 数据传输流程 mysql---->>hdfs---->>hive 数据从mysql表中取出,放到hdfs上(由targ…...

实验3-实时数据流处理-Flink
1.前期准备 (1)Flink基础环境安装 参考文章: 利用docker-compose来搭建flink集群-CSDN博客 显示为这样就成功了 (2)把docker,docker-compose,kafka集群安装配置好 参考文章: …...

深度学习实验十四 循环神经网络(1)——测试简单循环网络的记忆能力
目录 一、数据集构建 1.1数据集的构建函数 1.2加载数据集并划分 1.3 构建Dataset类 二、模型构建 2.1嵌入层 2.2SRN层 2.3模型汇总 三、模型训练 3.1 训练指定长度的数字预测模型 3.2 损失曲线展示 四、模型评价 五、修改 附完整可运行代码 实验大体步骤&#x…...

k8s部署odoo18(kubeshpere面板)
Postgresql部署 链接: kubesphere搭建 postgres15 因为我的是在另一台服务器使用kubesphere进行部署的,如果有和我一样情况的,可以参考上面的文档部署postgreasql。 注意事项: 因为odoo不允许使用postgresql的默认用户,也就是po…...

【模型对比】ChatGPT vs Kimi vs 文心一言那个更好用?数据详细解析,找出最适合你的AI辅助工具!
在这个人工智能迅猛发展的时代,AI聊天助手已经深入我们的工作与生活。你是否曾在选择使用ChatGPT、Kimi或是百度的文心一言时感到一头雾水?每款AI都有其独特的魅力与优势,那么,究竟哪一款AI聊天助手最适合你呢?本文将带…...

Java——容器(单例集合)(上)
一 容器介绍 容器,是用来容纳物体、管理物体。生活中,我们会用到各种各样的容器。如锅碗瓢盆、箱子和包等 程序中的“容器”也有类似的功能,用来容纳和管理数据。比如,如下新闻网站的新闻列表、教育网站的课程列表就是用“容器”来管理 视频…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
A2A JS SDK 完整教程:快速入门指南
目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库ÿ…...

Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...