数据结构算法-贪心算法

引言

贪心:人只要有 “需求“ ,都会有有点“贪“, 这种“贪“是一种选择,或者“”取舍“
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; 
}

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

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

相关文章

MicroPython STM32F4 RTC功能使用介绍

MicroPython STM32F4 RTC功能使用介绍 &#x1f516;STM32和ESP32 RTC功能差不多&#xff0c;相关篇《MicroPython ESP32 RTC功能使用介绍》&#x1f4cc;固件刷可参考前面一篇《STM32刷Micropython固件参考指南》&#x1f33f; 相关篇《Micropython STM32F4入门点灯》&#x1…

Aapche Dubbo 不安全的 Java 反序列化 (CVE-2019-17564)

漏洞描述 Apache Dubbo 是一个高性能的、基于 Java 的开源 RPC 框架。 Apache Dubbo 支持不同的协议&#xff0c;它的 HTTP 协议处理程序是 Spring Framework 的 .org.springframework.remoting.httpinvoker.HttpInvokerServiceExporter Spring Framework 的安全警告显示&am…

MySQL表连接

文章目录 MySQL内外连接1.内连接2.外连接&#xff08;1&#xff09;左外连接&#xff08;2)右外连接 3.简单案例 MySQL内外连接 1.内连接 内连接的SQL如下&#xff1a; SELECT ... FROM t1 INNER JOIN t2 ON 连接条件 [INNER JOIN t3 ON 连接条件] ... AND 其他条件;说明一下…

内测分发平台是否支持应用的微服务化部署

内测分发平台的微服务化部署支持是现代应用开发和部署的一个重要特性。首先我们得知道什么是微服务化部署都有哪些关键功能&#xff0c;如何实施微服务化的部署。下文以我自己理解总结了几点。 图片来源:news.gulufenfa.com 微服务是一种基于独立运行的小型服务来构建应用程序…

医学图像分割:U_Net 论文阅读

“U-Net: Convolutional Networks for Biomedical Image Segmentation” 是一篇由Olaf Ronneberger, Philipp Fischer, 和 Thomas Brox发表的论文&#xff0c;于2015年在MICCAI的医学图像计算和计算机辅助干预会议上提出。这篇论文介绍了一种新型的卷积神经网络架构——U-Net&a…

【浅尝C++】C++类的6大默认成员函数——构造、析构及拷贝构造函数

&#x1f388;归属专栏&#xff1a;浅尝C &#x1f697;个人主页&#xff1a;Jammingpro &#x1f41f;记录一句&#xff1a;好想摆烂&#xff0c;又好想学习~~ 文章前言&#xff1a;本篇文章简要介绍C类的构造函数、析构函数及拷贝构造函数&#xff0c;介绍每个小点时&#xf…

C语言公交车之谜(ZZULIOJ1232:公交车之谜)

题目描述 听说郑州紫荆山公园有英语口语角&#xff0c;还有很多外国人呢。为了和老外对上几句&#xff0c;这周六早晨birdfly拉上同伴早早的就坐上了72路公交从学校向紫荆山进发。一路上没事干&#xff0c;birdfly开始思考一个问题。 从学校到紫荆山公园共有n(1<n<20)站路…

Git本地库操作

对本地库的操作很少&#xff0c;我们学习1~6节即可&#xff0c;其他了解下。我们可以在idea中完成对本地库还有远程库的操作&#xff0c;可视化界面用起来更加舒适而且也不会混淆。 1. Git概述 Git 是一个免费的、开源的分布式版本控制系统&#xff0c;可以快速高效地处理从小…

Cesium 可视化深度纹理

Cesium 可视化深度纹理 // 创建纹理辅助器图元const textureHelper new TextureHelperPrimitive(viewer.scene)viewer.scene.primitives.add(textureHelper)viewer.scene.postRender.addEventListener(function () {const framebuffer viewer.scene.view.pickDepths[0]?.fra…

问题:vue2+elementui,tabs切换显示表格并设置表格选中行高亮失败

错误示范&#xff1a; 1.直接setCurrentRow失败&#xff08;this.currentRow是之前保存的表格当前选中行的数据&#xff09; this.$refs.table.setCurrentRow(this.currentRow);2.以为是表格没生成就执行了setCurrentRow导致设置不成功&#xff0c;所以使用了this.$nextTick&…

[网鼎杯 2020 朱雀组]Nmap

启动环境 结合题目首先就是要知道关于关于nmap命令 相关的命令-oN 标准保存 -oX XML保存 -oG Grep保存 -oA 保存到所有格式 -iL 读取文件内容&#xff0c;以文件内容作为搜索目标 -o 输出到文件 -sP Ping 扫描 还有许多 nmap命令https://blog.csdn.net/weixin_735627…

30.0/集合/ArrayList/LinkedList

目录 30.1什么是集合? 30.1.2为什么使用集合 30.1.3自己创建一个集合类 30.1.3 集合框架有哪些? 30.1.2使用ArrayList集合 30.2增加元素 30.3查询的方法 30.4删除 30.5 修改 30.6泛型 30.1什么是集合? 我们之前讲过数组&#xff0c;数组中它也可以存放多个元素。集合…

vue3 for循环创建的多个e-form 添加校验

v-for 创建 ref <el-form :model"item" :rules"state.rules" :ref"el > getRiskSpreadRef(el, index)" ></el-form>// 定义ref list const riskSpreadRefList ref<HTMLElement[]>([]);// ref存到数组 const getRiskSpread…

前端 计算机基础篇 ( 二 )

文章目录 websockt及原理ipv4和ipv6的区别线程和进程的区别cdn原理缓存所涉及的http状态码缓存的时候设置 no-store和no-cache和max-age0这几个有什么区别token一般存放在哪儿怎么设置强缓存和协商缓存强缓存&#xff1a;1. 使用 Cache-Control 头字段&#xff1a; 协商缓存&am…

竞赛选题 题目:基于LSTM的预测算法 - 股票预测 天气预测 房价预测

文章目录 0 简介1 基于 Keras 用 LSTM 网络做时间序列预测2 长短记忆网络3 LSTM 网络结构和原理3.1 LSTM核心思想3.2 遗忘门3.3 输入门3.4 输出门 4 基于LSTM的天气预测4.1 数据集4.2 预测示例 5 基于LSTM的股票价格预测5.1 数据集5.2 实现代码 6 lstm 预测航空旅客数目数据集预…

使用SpringBoot集成MyBatis对管理员的查询操作

增删改查中的查询操作&#xff0c;对所有的普通管理员进行查询操作。 效果展示&#xff1a; 不仅可以在打开页面时进行对管理员的自动查询操作&#xff0c;还可以在输入框进行查询。 首先是前端向后端发送POST请求&#xff0c;后端接收到请求&#xff0c;如果是有参数传到后端…

C语言--每日选择题--Day27

第一题 1. 对于代码段&#xff0c;问下面不可以表示a[1]地址的是&#xff08;&#xff09; int a[10]; A&#xff1a;&a[0] 1 B&#xff1a;a sizeof(int) C&#xff1a;(int*)&a 1 D&#xff1a;(int*)((char*)&a sizeof(int)) 答案及解析 A A&#xff1a;取到…

免费获取GPT-4的五种工具

不可否认&#xff0c;由OpenAI带来的GPT-4已是全球最受欢迎的、功能最强大的大语言模型&#xff08;LLM&#xff09;之一。大多数人都需要使用ChatGPT Plus的订阅服务去访问GPT-4。为此&#xff0c;他们通常需要每月支付20美元。那么问题来了&#xff0c;如果您不想每月有这笔支…

redis运维(十五) 集合

一 集合 ① 概念 集合的元素在redis里面的世界是member集合&#xff1a; setset集合当中不允许重复的元素&#xff0c;而且set集合当中元素是没有顺序的,不存在元素下标 ② sadd、smembers、srem ③ sismember、srandmember、spop、scard spop 命令用于移除集合中的指定 …

docker国内镜像加速

创建或修改 /etc/docker/daemon.json 文件&#xff0c;修改为如下形式 {"registry-mirrors": ["https://registry.docker-cn.com","http://hub-mirror.c.163.com","https://docker.mirrors.ustc.edu.cn"] } Docker中国区官方镜像htt…