当前位置: 首页 > news >正文

数据结构算法-贪心算法

引言

贪心:人只要有 “需求“ ,都会有有点“贪“, 这种“贪“是一种选择,或者“”取舍“
RTS(即时战略)游戏: 帝国时代里 首先确保拥有足够的人口 足够的粮食,足够的战略资源 足够的兵力才能发起一次“围剿”
当然 也可以边战斗 边收集资源 升级时代等等 你会发现,但选择升级时代 时,资源种类多了一些 兵种也会有一些变化 (好像在说废话…)当然只要能快一点 击败敌人 这样融合军事,收集资源 城建 模拟货币交易 的游戏 才是真正的玩 脑子游戏 (这是 个人定义 )
你能看出来哪里 贪心的选择?
人口;多一些劳动力
收集资源 人口一多 可以压榨(军阀模拟器?)哈哈,人要想为自己而活 是不能做到的 当然(美利坚)除外 恨不得自己…
为集体人民而活 短期来看没一点成果,但长期 看到会有点收获
这好比现实生活 短期投资 没一点回报,但只要时间充足 一定会一些回报
足够的战略资源 : 粮食中的大豆(帝国时代没有大豆) 作为战略资源 确定有点变态 那头恶臭味的鹰 引起了他的注意
兔子团购鹰豆,鹰反而说一些:由于天气xxx 推迟 结果买的是虚价 卖的 确是阴间价 这就是那鹰的作风 看不起兔子
只能说“从此我已八嘎呀路“这位原神玩家请你出去 不要再这里闹!

足够的兵力 :这不就是必备的 ,

升级时代: 满足一定的条件: 升级时代好处在于使用当前最新的科技 和最新的军种
食物 满足800 ,木材 1000 黄金(货币)500 统统满足了 …
随着时代的更变 若集体不前进 就会挨打的

开放世界类型也是一样的道理
以原神为例 当你选择了某个任务 必须做完为止中间不能跳过,才可以接下一个任务 当然原神是非常自由的 想打啥就打啥 缺啥补充啥.这样 才有乐趣这是所谓的动态平衡 原神有一个点 叫谋权篡位 ,神突然死 去,当人们面对自己危在旦夕璃月需要变成人的政权。也是人主导 并且化解这场危机当然也非常的末代皇帝 味道 钟离表示:我累了 守护你们这么多年了 我就得意使绊子 “我特意假死 看看情况没想到却 … 好吧,人毕竟是未来 到是便宜了,胡桃”…我选择以人身份活着 那也不错 派蒙:一个社会“废人” 调侃 确实正确 好在有往生堂胡堂主 做客卿 …

贪心算法核心思想

贪心:谋取自身的利益,做出不能改变想法,只能一直做下去直到找到 ,或者没找到

定义一种选择
这种选择可能能找到问题的解 (局部最优解)若不能找到问题的解(局部最优解)返回错误值 ,能找到问题的解(局部最优解)直接返回
这种选择找不到全局最优解,

比方:每次只看播放量 很高的视频作品 ,点赞量 很高 即使再拉也就短暂, 而不是长期
比如说:某一些电视剧角色看起来,风风光光,背后暗箱操作,结果为自己罪行买单(你们肯定知道我要说的是谁:高启强)
所以但凡人都会有私心想怎么搞最大化 以及风险小的利益

不考虑长久 只考虑当前如何最优

数据结构 图: 每次选择最近的顶点 作为深度优先遍历

贪心算法实现思路

钱币找零 大家非常不陌生,但移动支付打破了格局 让小偷都 只敢偷手机了 可得知信息安全重要性,
但钱包可能在一些老人可是还在用纸币,让我们回忆回忆如何通过纸币来找零钱

我们先不管五毛 只 找整
首先这些面值为 1块钱 2块钱 5块钱 10块钱 20块钱 50块钱 100块钱
但只是面值 有多少张 才是硬道理 总不能没有吧 那怎么发行 那怎么流通 ?
所以这个纸币的张数这就来 首先说明一下 银行怎么做我们就怎么做 交易限制 在5wRMB 每日
但我们比还有狠 直接 1块钱(20张) 2块钱(6张) 5块钱(3张) 10块钱 (6张) 20块钱(2张) 50块钱(3张) 100块钱 (5张)一共是807元 倘若给我找600块 若是从1块开始找 效率低下 你想想谁会用这种方法! 很明显最大 开始

在这里插入图片描述

贪心应用算法专区

#include<iostream>  
using namespace std;  // 定义一个常量N为7,表示纸币面额的数量  
const int N = 7;  // 定义一个数组paperMoney,存储纸币的面额  
const int  paperMoney[N] = { 1,2,5,10,20,50,100 };  
// 定义一个数组paperMoneyCount,存储每种面额纸币的数量  
const int paperMoneyCount[N] = { 10,2,3,1,2,3,5 };  // 定义一个函数change,输入是需要找零的金额,输出是需要多少张纸币  
// 这个函数用于计算找零所需的纸币数量  
int change(int Money) {  int num = 0; // 初始化纸币数量为0  for (int i = N - 1; i >= 0; i--){ // 从大到小遍历纸币面额  int currentPaperMoneyCounts =  Money / paperMoney[i] ; // 计算需要多少张当前面额的纸币  int PaperMoneyCounts = currentPaperMoneyCounts < paperMoneyCount[i] ? currentPaperMoneyCounts : paperMoneyCount[i]; // 如果当前面额的纸币数量不足,则使用全部数量  // 输出需要多少张当前面额的纸币  cout << "需要" << paperMoney[i] << "面值纸币" << "兑换 " << PaperMoneyCounts <<" 张" << endl;  Money -= PaperMoneyCounts* paperMoney[i]; // 从需要找零的金额中减去已经使用的当前面额纸币的总价值  num += PaperMoneyCounts; // 增加已经使用的纸币数量  if (Money<=0){ // 如果已经没有需要找零的金额,跳出循环  break;  }  }  if (Money>0){ // 如果最后还有需要找零的金额,说明无法找零,返回-1  num = -1;  }  return  num; // 返回需要的纸币数量或者-1(无法找零)  
}  // 主函数,程序的入口点  
int main(void) {  int Money; // 定义一个变量存储需要找零的金额  cout << "请输入需要找零的纸币:"; cin >> Money; const int ret = change(Money); // 调用change函数计算需要的纸币数量if (cin&&ret!=-1){ // 如果用户输入成功且没有无法找零的情况,输出需要的纸币数量  cout <<"需要" << ret << "张纸币才能找零" << endl;  }  else { cout << "找不开!" << endl;  }  return 0; 
}

相关文章:

数据结构算法-贪心算法

引言 贪心&#xff1a;人只要有 “需求“ &#xff0c;都会有有点“贪“&#xff0c; 这种“贪“是一种选择&#xff0c;或者“”取舍“ RTS&#xff08;即时战略&#xff09;游戏&#xff1a; 帝国时代里 首先确保拥有足够的人口 足够的粮食&#xff0c;足够的战略资源 足够的…...

【云备份】数据管理模块

文章目录 1. 数据管理模块要管理什么数据&#xff1f;2. 数据管理模块如何管理数据&#xff1f;3. 数据管理模块的具体实现BackupInfo 数据信息类NewBackupInfo —— 获取各项属性信息 DataManager 数据管理类构造函数析构函数insert —— 新增update —— 修改GetOneByURL——…...

C++ :const修饰成员函数

常函数&#xff1a; 常函数&#xff1a; 成员函数后加const后我们称为这个函数为常函数 常函数内不可以修改成员属性 成员属性声明时加关键字mutable后&#xff0c;在常函数中依然可以修改 属性可修改&#xff1a; class Person { public: void showPerson() …...

论文阅读:“Model-based teeth reconstruction”

文章目录 AbstractIntroductionTeeth Prior ModelData PreparationParametric Teeth Model Teeth FittingTeeth Boundary Extraction Reference Abstract 近年来&#xff0c;基于图像的人脸重建方法日趋成熟。这些方法可以捕捉整个面部或面部特定区域&#xff08;如头发、眼睛…...

Web 安全之证书透明(Certificate Transparency)详解

目录 证书透明性的概念 数字证书和颁发机构 证书透明的起源 证书透明的工作原理 证书透明的实现方法 证书透明的优点 浏览器和客户端对证书透明的支持情况 小结 证书透明&#xff08;Certificate Transparency, CT&#xff09;是网络安全领域中的一个重要概念&#xff…...

智能优化算法应用:基于蜻蜓算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于蜻蜓算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于蜻蜓算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.蜻蜓算法4.实验参数设定5.算法结果6.参考文献7.MATLAB…...

【古诗生成AI实战】之二——项目架构设计

[1] 项目架构 在我们深入古诗生成AI项目的具体实践之前&#xff0c;让我们首先理解整个项目的架构。本项目的代码流程主要分为三个关键阶段&#xff1a; 1、数据处理阶段&#xff1b;   2、模型训练阶段&#xff1b;   3、文本生成阶段。 第一步&#xff1a;在数据处理阶段…...

动态网页从数据库取信息,然后展示。

把数据库的驱动放在bin目录下。 通过servlet 读取数据库的内容&#xff0c;生成session,然后跨页面传给展示页。 package src;import java.io.IOException; import java.io.PrintWriter; import java.sql.Connection; import java.sql.DriverManager; import java.sql.ResultSe…...

单片机学习3——数码管

数码管&#xff0c;根据内部结构&#xff0c;可分为共阴极数码管和共阳极数码管。七段发光管加上一个小数点&#xff0c;共计8段。因此&#xff0c;我们对它编程的时候&#xff0c;刚好是用一个字节。 数码管的显示方式&#xff1a; 1&#xff09;静态显示&#xff1b; 2&…...

数据库表结构导出成Excel或Word格式

前言 该工具主要用于导出excel、word&#xff0c;方便快速编写《数据库设计文档》&#xff0c;同时可以快速查看表的结构和相关信息。 本博客仅作记录&#xff0c;最新源码已经支持多种数据库多种格式导出&#xff0c;有兴趣的可移步源码作者地址&#xff1a;https://gitee.co…...

School training competition ( Second )

A. Medium Number 链接 : Problem - 1760A - Codeforces 就是求三个数的中位数 : #include<bits/stdc.h> #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl \nusing namespace std; typedef long long LL; const int N 2e510;inline void …...

深度解析 Docker Registry:构建安全高效的私有镜像仓库

文章目录 什么是Docker Registry&#xff1f;Docker Hub vs. 私有RegistryDocker Hub&#xff1a;私有Registry&#xff1a; 如何构建私有Docker Registry&#xff1f;步骤一&#xff1a;安装Docker Registry步骤二&#xff1a;配置TLS&#xff08;可选&#xff09;步骤三&…...

leetcode 不同的二叉搜索树

给你一个整数 n &#xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种&#xff1f;返回满足题意的二叉搜索树的种数。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;5 示例 2&#xff1a; 输入&#xff1a;n 1 输出&#xff1a;…...

通俗易懂的spring Cloud;业务场景介绍 二、Spring Cloud核心组件:Eureka 、Feign、Ribbon、Hystrix、zuul

文章目录 通俗易懂的spring Cloud一、业务场景介绍二、Spring Cloud核心组件&#xff1a;Eureka三、Spring Cloud核心组件&#xff1a;Feign四、Spring Cloud核心组件&#xff1a;Ribbon五、Spring Cloud核心组件&#xff1a;Hystrix六、Spring Cloud核心组件&#xff1a;Zuul七…...

大数据预处理技术

文章目录 前言 大数据技术成为前沿专业 也是现在甚至未来的朝阳产业&#xff0c;大数据有分别是 数据预处理 数据存储 大数据处理和分析 数据可视化 部分组成 &#xff0c;大数据行业有数据则称王&#xff0c;大数据的核心是数据本身 怎么获取有价值的数据呢&#xff1f;本章讲…...

跳表的学习记录

跳表&#xff08;Skip List&#xff09;是一种数据结构&#xff0c;它通过在多个层次上添加额外的前向指针来提高有序数据的搜索效率。跳表与其他常见的有序数据结构&#xff08;如二叉搜索树、平衡树如AVL树和红黑树、B树等&#xff09;相比&#xff0c;具有其独特的优缺点&am…...

电子学会C/C++编程等级考试2022年09月(二级)真题解析

C/C++等级考试(1~8级)全部真题・点这里 第1题:统计误差范围内的数 统计一个整数序列中与指定数字m误差范围小于等于X的数的个数。 时间限制:5000 内存限制:65536输入 输入包含三行: 第一行为N,表示整数序列的长度(N <= 100); 第二行为N个整数,整数之间以一个空格分…...

如何使用nginx部署静态资源

Nginx可以作为静态web服务器来部署静态资源&#xff0c;这个静态资源是指在服务端真实存在&#xff0c;并且能够直接展示的一些文件数据&#xff0c;比如常见的静态资源有html页面、css文件、js文件、图片、视频、音频等资源相对于Tomcat服务器来说&#xff0c;Nginx处理静态资…...

lua的gc原理

lua垃圾回收(Garbage Collect)是lua中一个比较重要的部分。由于lua源码版本变迁&#xff0c;目前大多数有关这个方面的文章都还是基于lua5.1版本&#xff0c;有一定的滞后性。因此本文通过参考当前的5.3.4版本的Lua源码&#xff0c;希望对Lua的GC算法有一个较为详尽的探讨。 L…...

redis作为缓存详解

目录 前言&#xff1a; 为什么说关系型数据库性能不高 如何提高MySQL并发量 缓存更新策略 定期更新 实时更新 内存淘汰策略 Redis内置的淘汰策略 缓存常见问题 缓存预热 缓存穿透 缓存雪崩 缓存击穿 前言&#xff1a; 对于缓存的理解&#xff0c;缓存目的就是为了…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...