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

算法之贪心算法

news 2026/2/7 16:58:21

定义

总是做出当前最好的选择，期望通过局部最优选择得到全局最优的解决方案。

适用标准

  1. 贪心选择性质。
    原问题的整体最优解可以通过一系列局部最优的选择得到。这种选择依赖于已做出的选择，不依赖于未做出的选择。贪心算法解决的问题，在程序运行过程中无回溯过程。
  2. 最优子结构性质。
    一个问题的最优解包含其子问题的最优解。

求解步骤

  1. 贪心策略。
    根据求解目标，选择当前最优的一个。
  2. 局部最优解。
    根据贪心策略，一步步得到局部最优解。
  3. 全局最优解。
    所有局部最优解，合成原问题的最优解，

示例

给你一堆苹果，每个苹果重量不同[90, 120, 100, 160, 90, 80, 90, 100]，你能吃500的苹果，求，最多吃多好个。

  1. 贪心策略，每次吃剩余苹果中重量最小的那个
  2. 局部最优解。
    • 第1个吃80，还能吃420
    • 第2个吃90，还能吃330
    • 第3个吃90，还能吃240
    • 第4个吃90，还能吃150
    • 第5个吃100，还能吃50
    • 剩余苹果中最小的为100，吃不了，结束
  3. 全局最优解
    最多吃5个苹果，依次为80,90,90,90,100

参考《算法训练营》

相关文章：

算法之贪心算法

定义 总是做出当前最好的选择，期望通过局部最优选择得到全局最优的解决方案。 适用标准 贪心选择性质。 原问题的整体最优解可以通过一系列局部最优的选择得到。这种选择依赖于已做出的选择，不依赖于未做出的选择。贪心算法解决的问题，在程…...

编程日记 2023/6/12 6:44:02

Maven 基础

博文目录 文章目录 Maven基础概念生命周期 - Build Lifecycle阶段 - Build Phase目标 - Plugin goals默认目标绑定Clean 生命周期Default 生命周期Site 生命周期 插件 - Plugin POM（Project Object Model）Super POM项目继承 - Project Inheritance项目聚…...

编程日记 2023/6/12 6:39:01

算法刷题-哈希表-两数之和

两数之和 1. 两数之和思路总结其他语言版本 1. 两数之和 力扣题目链接 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中…...

编程日记 2023/6/12 6:34:00

kotlin学习（一）基本概念、数据对象类型、控制流程、空值检验、类与接口

文章目录 认识Kotlin跨平台特性语言类型java的语言类型kotlin的运行原理 hello world 基本概念程序入口数据与对象类型 和 显式数字转换浮点类型位运算AnyUnitNothing 声明变量只读变量 val与可变变量var查看Kotlin字节码 fun（方法 / 函数）函数参数默认值…...

编程日记 2023/6/12 6:29:00

【Linux】Docker部署镜像环境 （持续更新ing）

防火墙 1、查看防火墙状态 sudo systemctl status ufw 2、开启防火墙 sudo systemctl start ufw 3、关闭防火墙 sudo systemctl stop ufw 4、开机禁止开启防火墙 sudo systemctl disabled ufw 5、开启自启防火墙 sudo systemctl enabled ufw Elasticsearch 1、安装指定版本 比…...

编程日记 2023/6/12 6:23:59

Jtti：如何打开云服务器的8082端口

如何打开云服务器的8082端口? 第一步：登录云服务器 首先，我们需要登录到我们的云服务器。可以使用SSH、控制台等方式进行登录。登录成功后，我们可以在终端上看到服务器的控制台。 第二步：编辑防火墙规则 打开终端后，我…...

编程日记 2023/6/12 6:18:58

有关 string 类的练习（下）

目录 一、反转字符串 II 二、反转字符串中的单词 III 三、找出字符串中第一个只出现一次的字符 四、字符串相乘 五、把字符串转换成整数 一、反转字符串 II 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转…...

编程日记 2023/6/12 6:13:57

XuperChain搭建+报错+注意事项

安装依赖 golang 这里安装的是15-17版本 wget -c https://dl.google.com/go/go1.15.2.linux-amd64.tar.gz -O - | sudo tar -xz -C /usr/local 添加环境变量 这个可以通过添加下面的行到/etc/profile文件（系统范围内安装）或者$HOME/.profile文件（当前用户安装 vim /etc…...

编程日记 2023/6/12 6:08:55

【伏羲八卦图】（PythonMatlab实现）

目录 1 与达尔文对话 2 与老子对话 2.1 Python实现 2.2 Matlab实现 1 与达尔文对话 140年前，1858年7月1日，达尔文在英伦岛发表了自己有关自然选择的杰出论文。他提出，生物的发展规律是物竞天择。经过物竞，自然界选择并存留最具…...

编程日记 2023/6/12 6:03:54

ruoyi数据权限学习

思路 用户关联了角色（用户可以关联多个角色），给角色设置数据权限分类，数据权限分类有如下5种： 全部数据权限 - DATA_SCOPE_ALL自定数据权限 - DATA_SCOPE_CUSTOM部门数据权限 - DATA_SCOPE_DEPT部门及以下数据权限 -…...

编程日记 2023/6/12 5:58:54

WPF中实现动态导航

主页面 <mah:MetroWindowx:Class"Kx.View.MyMainView"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/expression/bl…...

编程日记 2023/6/12 5:53:53

day16 | 104.二叉树的最大深度、111.二叉树的最小深度、 222.完全二叉树的节点个数

目录&#xff1a; 链接 题目链接&#xff1a; https://leetcode.cn/problems/maximum-depth-of-binary-tree/ https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/ https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/ 解题及思路学习 104…...

编程日记 2023/6/12 5:48:51

Spring Boot + Vue3前后端分离实战wiki知识库系统＜八＞--分类管理功能开发二

接着上一次Spring Boot Vue3 前后端分离 实战 wiki 知识库系统&#xff1c;七&#xff1e;--分类管理功能开发的分类功能继续完善。 分类编辑功能优化&#xff1a; 概述&#xff1a; 现在分类编辑时的界面长这样&#xff1a; 很明显目前的父分类的展现形式不太人性&#xf…...

编程日记 2023/6/12 5:43:50

Python入门（十八）类（一）

类&#xff08;一&#xff09; 1.面向对象概述2.创建和使用类2.1 创建dog类2.2 根据类创建实例2.3 创建多个实例 1.面向对象概述 面向对象编程是最有效的软件编写方法之一。在面向对象编程中&#xff0c;你编写表示现实世界中的事物和情景的类&#xff0c;并基于这些类来创建对…...

编程日记 2023/6/12 5:38:49

c# 从零到精通-定义一个结构

c# 从零到精通-定义一个结构 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Test01 { class Program { public struct Rect//定义一个矩形结构 { public double width;//矩形的宽 public double height;//矩形的高 /// …...

编程日记 2023/6/12 5:33:49

检信ALLEMOTION非接触式心理情绪测评系统

1 名称&#xff1a;检信ALLEMOTION多维度心理情绪测评系统 2 用途&#xff1a;用于群体性人群心理情绪早期筛查&#xff0c;以及个人心理障碍辅助诊断,同时传统心理量表诞生已经100多年历史&#xff0c;在人工智能及大数据推动下&#xff0c;必然推动心理健康行业的产业变革与…...

编程日记 2023/6/12 5:28:48

20道嵌入式经典面试题（附答案）

1.嵌入式系统中经常要用到无限循环&#xff0c;如何用C编写死循环 答&#xff1a;while(1){} 或者 for(;;) 2.程序的局部变量存在于哪里&#xff0c;全局变量存在于哪里&#xff0c;动态申请数据存在于哪里。 答&#xff1a;程序的局部变量存在于栈区&#xff1b;全局变量存在…...

编程日记 2023/6/12 5:23:46

python学习-代码调试器

目录 为什么学习调试器Pycharm Debugger示例所用代码布局调试工具栏 Debug Bar程序控制工具栏 pdb查看源代码 l list查看当前函数源代码 ll longlist打印变量 p查看调用栈w where向上移动当前帧 u up向上移动当前帧 d down运行当前行代码,在第一个可以停止的位置停下 s step继续…...

编程日记 2023/6/12 5:18:45

第十一章 综合推理

第十一章　综合推理 第一节　综合推理-排序 题-综合推理-分类1-排序 甲、乙、丙、丁四人的国籍分别为英国、俄国、法国、日本。乙比甲高&#xff0c;丙更矮&#xff1b;英国人比俄国人高&#xff0c;法国人最高&#xff1b;日本人比丁高。 这四个人的国籍是&#xff1a; A.甲…...

编程日记 2023/6/12 5:13:44

嵌入式开发之设置寄存器中指定位

0 Preface/Foreword 嵌入式开发&#xff0c;位操作是常用的运算&#xff0c;读写对应寄存器指定位从而设置不同的功能。 1 设置寄存器中的任意位 1.1 清零 举例&#xff0c;假设一个寄存器名字为FUNCCON&#xff0c;地址为0x00008000,该寄存器长度为4个byte。 #define FUNC…...

编程日记 2023/6/12 5:08:44

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

编程新知 2026/2/5 4:33:58

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

编程新知 2026/1/11 2:37:51

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

编程新知 2026/1/26 1:54:23

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

编程新知 2026/1/31 6:12:33

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

编程新知 2026/1/31 12:52:29

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

编程新知 2026/1/31 23:25:09

【Go语言基础【12】】指针：声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

编程新知 2025/6/21 2:18:57

【Redis】笔记｜第8节｜大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

编程新知 2026/1/26 3:45:28

虚拟电厂发展三大趋势：市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

编程新知 2025/12/20 18:09:59

RSS 2025｜从说明书学习复杂机器人操作任务：NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

编程新知 2026/1/31 5:30:51