贪心算法理论
系列博客目录
文章目录
- 系列博客目录
- 贪心算法 (Greedy Algorithm)
- 贪心算法的特点
- 贪心算法的适用条件
- 常见的贪心算法问题
- 贪心算法的步骤
- 贪心算法示例:活动选择问题
- 贪心算法的优缺点
贪心算法 (Greedy Algorithm)
贪心算法是一种在每一步选择中都采取当前状态下最优的选择,从而希望得到全局最优解的算法。贪心算法的基本思想是通过局部最优的选择来逐步接近全局最优解。它并不回溯,且每一步的选择只基于当前信息,不考虑后续可能的影响。
贪心算法的特点
- 局部最优选择:在每一步选择中,贪心算法都会选择当前看来最优的选项,不会考虑全局的影响。
- 无后悔:选择一旦做出,就不会再回头修改。
- 贪心选择性质:贪心算法的每一个局部最优选择并不保证全局最优,适用的情况需要问题具有贪心选择性质和最优子结构。
贪心算法的适用条件
- 贪心选择性质:通过局部最优的选择可以得到全局最优解。
- 最优子结构:问题的最优解包含其子问题的最优解。即,通过递归求解子问题来得到最终的最优解。
常见的贪心算法问题
-
活动选择问题(Activity Selection Problem):给定一组活动及其开始时间和结束时间,选择最多的活动,使得它们相互不冲突。
-
背包问题(0-1背包问题的贪心解法):虽然 0-1 背包问题不能用贪心算法获得最优解,但在某些变种(如分数背包问题)中,贪心算法能够得到最优解。
-
哈夫曼编码(Huffman Coding):一种用于数据压缩的算法,利用贪心选择构建最优的前缀码。
-
最小生成树问题(Kruskal算法、Prim算法):通过贪心选择构建图的最小生成树。
-
单源最短路径问题(Dijkstra算法):用贪心算法求解从一个顶点到所有其他顶点的最短路径。
贪心算法的步骤
- 选择:在当前问题的状态下,选择一个看起来最优的解。
- 可行性检查:检查所选择的解是否满足约束条件。
- 选择结果:将选择的解加入到当前解的集合中。
- 问题规模减少:更新问题状态,减少问题的规模,进入下一个选择阶段。
- 重复:继续执行选择,直到满足停止条件。
贪心算法示例:活动选择问题
假设有一组活动,每个活动有一个开始时间和结束时间,目标是选择不冲突的活动数量最多的子集。
输入:
活动的开始时间和结束时间,例如:
活动 1: (1, 4)
活动 2: (2, 5)
活动 3: (3, 6)
活动 4: (5, 7)
活动 5: (8, 9)
贪心选择步骤:
-
按结束时间排序:将活动按结束时间排序,以确保每次选择结束时间最早的活动。
排序后的活动:活动 1 (1, 4),活动 2 (2, 5),活动 3 (3, 6),活动 4 (5, 7),活动 5 (8, 9) -
选择活动:
- 选择活动 1,结束时间为 4。
- 下一步选择活动 4(活动 2 和活动 3与活动 1冲突),结束时间为 7。
- 最后选择活动 5,结束时间为 9。
输出:
最多的活动是活动 1、活动 4 和活动 5,数量为 3。
贪心算法的优缺点
优点:
- 实现简单:贪心算法通常实现简单,容易理解。
- 效率高:很多贪心算法的时间复杂度较低,通常是线性的或对数级别的,适用于大规模问题。
缺点:
- 不能保证最优解:贪心算法并不总是能找到问题的最优解,特别是对于复杂问题(如 0-1 背包问题)。
- 不适用于所有问题:只有满足贪心选择性质和最优子结构的情况,贪心算法才会有效。
总结
贪心算法是一种适用于特定类型问题的策略,通过选择局部最优解来构造全局最优解。它简单且高效,但并不是所有问题都能通过贪心算法获得最优解,因此在使用时需要确保问题满足贪心算法的适用条件。
相关文章:
贪心算法理论
系列博客目录 文章目录 系列博客目录贪心算法 (Greedy Algorithm)贪心算法的特点贪心算法的适用条件常见的贪心算法问题贪心算法的步骤贪心算法示例:活动选择问题贪心算法的优缺点 贪心算法 (Greedy Algorithm) 贪心算法是一种在每一步选择中都采取当前状态下最优的…...
前端项目扫描漏洞整改的解决方案,附带部分漏洞的解决方法。
天崩开局 最近项目开始了漏洞扫描,于是乎 哎嘿嘿。。。 我直接彻底疯狂!!!! 我真的受不了了,这破班谁爱上谁上!依赖开发的锅,为什么要我来背。 在这里点名批评一下 inflight&#…...
brew安装NVM新手教程
首先确保macos下已安装好brew,搜索nvm资源代码: brew search nvm 演示效果图如下: 安装命令 brew install nvm 卸载命令 brew uninstall node 安装完成后提示如下: 直接命令行执行下代码的代码 export NVM_DIR"$HOME/.…...
Open3D (C++) 生成任意2D椭圆点云
目录 一、算法原理二、代码实现三、结果展示一、算法原理 椭圆标准参数方程为: x = a ∗ c o s ( t ) y = b ∗...
前端框架Vue3项目实战(基于Vue3实现一个小相册)
下面是是对Vue3操作的一个项目实战 下面代码是html的基本骨架(没有任何的功能): <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <title>相册</title> <style&…...
【Git系列】利用 Bash 脚本获取 Git 最后一次非合并提交的提交人
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
启动tomcat报错./startup.sh: Permission denied
报错解释: 这个错误表明你正在尝试启动Tomcat服务器,但是没有足够的权限来执行startup.sh脚本。 解决方法: 使用chmod命令修改脚本的权限,使得用户具有执行权限。 chmod x /path/to/tomcat/bin/startup.sh 或者 chmod x /path…...
【开篇】.NET开源 ORM 框架 SqlSugar 系列
.NET开源 ORM 框架 SqlSugar 系列 【开篇】.NET开源 ORM 框架 SqlSugar 系列【入门必看】.NET开源 ORM 框架 SqlSugar 系列【实体配置】.NET开源 ORM 框架 SqlSugar 系列【Db First】.NET开源 ORM 框架 SqlSugar 系列【Code First】.NET开源 ORM 框架 SqlSugar 系列【数据事务…...
【机器学习】支持向量机SVR、SVC分析简明教程
关于使用SVM进行回归分析的介绍很少,在这里,我们讨论一下SVR的理论知识,并对该方法有一个简明的理解。 1. SVC简单介绍 SVR全称是support vector regression,是SVM(支持向量机support vector machine)对回…...
EasyDSS视频推拉流技术的应用与安防摄像机视频采集参数
安防摄像机的视频采集参数对于确保监控系统的有效性和图像质量至关重要。这些参数不仅影响视频的清晰度和流畅度,还直接影响存储和网络传输的需求。 安防摄像机图像效果的好坏,由DSP处理器和图像传感器sensor决定,如何利用好已有的硬件资源&…...
【详细介绍及演示】Flink之checkpoint检查点的使用
目录 一、介绍 二、 设置checkpoint检查点演示 1、 代码演示 2、测试代码效果 3、查看快照情况 编辑 三、在集群上运行 1、第一次运行 2、第二次运行 四、自定义检查点savePoint 1、提交一个flink job 打成jar包 2、输入一些数据,观察单词对应的数字的…...
使用uni-app进行开发前准备
使用uni-app进行开发,需要遵循一定的步骤和流程。以下是一个详细的指南,帮助你开始使用uni-app进行开发: 一、开发环境搭建 安装Node.js: 首先,从Node.js的官方网站(https://nodejs.org/)下载并…...
deepin 安装 chrome 浏览器
deepin 安装 chrome 浏览器 最近好多小伙伴儿和我说 deepin 无法安装最新的谷歌浏览器 其实是因为最新的 谷歌浏览器 其中的一个依赖需要提前安装 提前安装依赖然后再安装谷歌浏览器就可以了 安装 fonts-liberationsudo apt -y install fonts-liberation安装 chrome 浏览器sudo…...
Vue-01
Vue框架 Vue官网: Vue.js 框架 数据模型和view的通信就是依靠viewmodel的关键。 目前主流版本仍然是vue2版本。 Vue快速入门 1.新建一个HTML文件,引入Vue.js文件。Vue.js文件是官方引入的一个文件,我们如果要使用Vue就必须引入这个文件。…...
【Oracle】个人收集整理的Oracle常用SQL及命令
【建表】 create table emp( id number(12), name nvarchar2(20), primary key(id) ); 【充值一】 insert into emp select rownum,dbms_random.string(*,dbms_random.value(6,20)) from dual connect by level<101; 【充值二】 begin for i in 1..100 loop inser…...
11.28.2024刷华为OD
文章目录 C-100-5键键盘(extend来加入list后尾)题目2语法知识记录 C-100-5键键盘(extend来加入list后尾) 考虑所有情况extend来加入clip数组内容到screen 【】 题目2 链接 代码 语法知识记录...
【S500无人机】--地面端下载
之前国庆的时候导师批了无人机,我们几个也一起研究了几次,基本把无人机组装方面弄的差不多了,还差个相机搭载,今天我们讲无人机的调试 硬件配置如下 首先是地面端下载,大家可以选择下载: Mission Planne地…...
Redis2——协议与异步方式
文章目录 Redis2——协议与异步方式1. Redis Pipeline2. Redis事务2.1 无锁事务控制(乐观事务控制)2.2 事务语句与lua脚本2.3 事务特性ACID 3. 通信方式3.1 hiredis库3.2 同步连接3.3 异步连接3.3.1 hiredis管理监听事件接口3.3.2 hiredis libevent3.3.…...
面向下一代技术,遨游通讯如何助力北斗规模化应用提速?
近日,纪念北斗卫星导航系统工程建设三十周年座谈会在北京隆重召开,据悉,我国计划在2035年完成下一代北斗系统的建设。“北斗牵手,守护永久”北斗三号短报文公众应用商用试验启动仪式也于本月在雄安新区举行,会上透露&a…...
vue实现echarts饼图自动轮播
echarts官网:Examples - Apache ECharts echartsFn.ts 把echarts函数封装成一个文件 import * as echarts from "echarts";const seriesData [{"value": 12,"name": "过流报警"},{"value": 102,"name&qu…...
数据分析的尽头是web APP?
数据分析的尽头是web APP? 在做了一些数据分析的项目,也制作了一些数据分析相关的web APP之后,总结自己的一些想法和大家分享。 1.web APP是呈现数据分析结果的另外一种形式。 数据分析常见的结果是数据分析报告,可以是PPT或者…...
windows电脑上安装树莓派操作系统
在Windows电脑上安装树莓派通常涉及以下几个步骤:准备安装工具、下载树莓派系统镜像、烧录系统到SD卡、配置树莓派以及远程连接(如果需要无显示器操作)。以下是详细的步骤说明: 一、准备安装工具 安装树莓派官方烧录工具: 下载并安装Raspberry Pi Imager。这是一个官方的…...
openssl编译安装升级为新版本
文章目录 1、下载版本2、上传并解压3、编译安装4、验证 1、下载版本 https://www.openssl.org/source/old/1.1.1/ 2、上传并解压 tar zxvf openssl-1.1.1s.tar.gz 3、编译安装 注意:要提前安装好 gcc perl cd openssl-1.1.1s ./config --prefix/usr/local/open…...
监控视频汇聚平台:Liveweb视频监控管理平台方案详细介绍
Liveweb国标视频综合管理平台是一款以视频为核心的智慧物联应用平台。它基于分布式、负载均衡等流媒体技术进行开发,提供广泛兼容、安全可靠、开放共享的视频综合服务。该平台具备多种功能,包括视频直播、录像、回放、检索、云存储、告警上报、语音对讲、…...
【论文复现】基于BERT的语义分析实现
📝个人主页🌹:Eternity._ 🌹🌹期待您的关注 🌹🌹 ❀ WRN: 宽度残差网络 概述语义分类文本分类情感分类 实现原理 核心逻辑pre_deal.pytrain.pytest_demo.py 实现方式&演示效果训练阶段测试阶…...
SMOTE | 使用SMOTE算法来处理不平衡数据的问题
需求 在学习机器学习识别信用卡欺诈交易这个项目的时候,样本数据集非常不平衡: data_df_new[Class].value_counts()0: 正常 1:欺诈 在这里了解到了SMOTE算法: 过采样(Oversampling) 过采样是…...
week 9 - Entity-Relationship Modelling
一、数据库设计的重要性 • 设计数据库可使查询更高效、简洁。 • 减少数据冗余(data redundancy),提升表的整洁性。 二、Key Components of ER Modelling 实体-关系建模的基本构成 1. 实体(Entity):表…...
彻底理解如何保证ElasticSearch和数据库数据一致性问题
一.业务场景举例 需求: 一个卖房业务,双十一前一天,维护楼盘的运营人员突然接到合作开发商的通知,需要上线一批热门的楼盘列表,上传完成后,C端小程序支持按楼盘的名称、户型、面积等产品属性全模糊搜索热门…...
JS基础知识05-对象、Ajax、JSON
目录 一、对象 1.1.对象(Object) 1.创建对象 对象的常用方法 1.2.Math对象 1.数学常数 2.数学函数 3.随机数生成 4.对数方法 1.3.Date对象 创建Date对象 获取日期和时间的方法 设置日期和时间的方法 日期的格式化方法 二、Ajax 1.创建XM…...
pandas 读写excel
在Python中,使用Pandas库读写Excel文件是一个常见的操作。Pandas提供了read_excel和to_excel方法来分别实现读取和写入Excel文件的功能。以下是一些基本的示例: ### 读取Excel文件 python import pandas as pd # 读取Excel文件 df pd.read_excel(pat…...
Windows加固脚本
echo off REM 清屏 cls title 安全策略设置批处理 color f0 echo **************************************** echo write by afei echo https://www.jianshu.com/u/ea4c85fbe8c7 echo **************************************** pause cls color 3f echo ********************…...
28.100ASK_T113-PRO Linux+QT 显示一张照片
1.添加资源文件 2. 主要代码 #include "mainwindow.h" #include "ui_mainwindow.h" #include <QImage> #include <QPixmap>MainWindow::MainWindow(QWidget *parent) :QMainWindow(parent),ui(new Ui::MainWindow) {ui->setupUi(this);QIm…...
Vue中的计算属性和监听属性
在Vue中,计算属性和监听属性是两种非常有用的功能,它们可以帮助我们更好地管理数据和响应数据的变化。 计算属性 计算属性是基于它们的依赖进行缓存的。只有当依赖发生变化时,计算属性才会重新计算。这使得计算属性非常适合用于执行昂贵的计…...
基于vite创建的react18项目的单元测试
题外话 最近一个小伙伴进了字节外包,第一个活就是让他写一个单元测试。 嗯,说实话,在今天之前我只知道一些理论,但是并没有实操过,于是我就试验了一下。 通过查询资料,大拿们基本都说基于vite的项目&…...
网络——HTTP与HTTPS三次握手和四次挥手
HTTP协议本身并不直接处理TCP连接的建立和关闭,这些是由底层的TCP协议来完成的。但是,由于HTTP通常运行在TCP之上,因此理解TCP的三次握手(用于建立连接)和四次挥手(用于关闭连接)对于理解HTTP通…...
自然语言处理:第六十六章 17 种 prompt engineering 方法大集合
本人项目地址大全:Victor94-king/NLP__ManVictor: CSDN of ManVictor 原文地址:17 种 prompt engineering 方法大集合 写在前面: 笔者更新不易,希望走过路过点个关注和赞,笔芯!!! 写在前面: 笔者更新不易,希望走过路…...
MySQL —— MySQL 程序
目录 前言 一、MySQL 程序简介 二、mysqld -- MySQL 服务器 三、mysql -- MySQL 客户端 1. mysql 客户端简介 2. mysql 客户端选项 (1)指定选项的方式 (2)mysql 客户端命令常用选项 (3)在命令行中使…...
AI蛋白质设计与人工智能药物设计
AI蛋白质设计与人工智能药物设计 AI蛋白质设计 一、蛋白质相关的深度学习简介 1.基础概念 1.1.机器学习简介:从手写数字识别到大语言模型 1.2.蛋白质结构预测与设计回顾 1.3.Linux简介 1.4.代码环境:VS code和Jupyter notebook* 1.5.Python关键概…...
Java基础之控制语句:开启编程逻辑之门
一、Java控制语句概述 Java 中的控制语句主要分为选择结构、循环结构和跳转语句三大类,它们在程序中起着至关重要的作用,能够决定程序的执行流程。 选择结构用于根据不同的条件执行不同的代码路径,主要包括 if 语句和 switch 语句。if 语句有…...
安装Fcitx5输入框架和输入法自动部署脚本(来自Mark24)-Ubuntu通用
在Ubuntu22.04上安装rime中文输入法的基本教程 上述文章接近废弃。 使用新逻辑配置基本的Fcitx5的输入法。 安装 第一步,下载相关组件 sudo nala install vim sudo nala install ruby sudo nala install fcitx5-rime第二步,设置语言为Fcitx5 而非 默认…...
软件无线电(SDR)的架构及相关术语
今天简要介绍实现无线电系统调制和解调的主要方法,这在软件定义无线电(SDR)的背景下很重要。 外差和超外差 无线电发射机有两种主要架构——一种是从基带频率直接调制到射频频率(称为外差),而第二种超外差是通过两个调制阶段来实…...
刷题分享11_30
刷题分享 1.(力扣216)这是一道回溯算法的经典题目。对于回溯算法,一般backtracking是没有返回值的,参数也比较不固定,需要根据每个题的特点来具体分析。这道题因为不能取到重复元素,所以需要额外加一个参数startindex,…...
Java技术复习提升 17反射
本章涉及到框架开发中必用的反射以及常用方法 很重要 注重理解并实践 第17章 反射 17.1 一个需求引出反射 package com.fsl; public class Cat {private String name "招财猫";public int age 10; //public的public Cat() {} //无参构造器public Cat(String name)…...
Python中的字符串
Python中的字符串 在Python中,字符串是用于表示文本数据的基本数据类型。字符串可以包含字母、数字、符号和空格等字符。Python提供了多种方式来定义和操作字符串。 字符串的定义 在Python中,字符串可以用单引号 或双引号 "" 括起来。例如…...
B站狂神说Mybatis+Spring+SpringMVC整合理解(ssm框架整合)
文章目录 0.写在前面(对mybatis,spring的理解)(不看可跳过)0.1 为什么需要mybatis0.2 为什么需要spring0.3为什么需要springmvc 1.新建ssmbuild数据库2.新建Maven项目3.初始化步骤3.1 配置下载maven依赖,构建资源导出3.2 连接数据库3.3建包&a…...
python:文件操作
一、文件路径 在Windows系统中,每个磁盘都有自己的根目录,用分区名加反斜杠来表示。我们定位文件的位置有两种方法,一种是绝对路径,另一种是相对路径。绝对路径是从根目录出发的路径,路径中的每个路径之间用反斜杠来分…...
ECharts柱状图-极坐标系下的堆叠柱状图,附视频讲解与代码下载
引言: 在数据可视化的世界里,ECharts凭借其丰富的图表类型和强大的配置能力,成为了众多开发者的首选。今天,我将带大家一起实现一个柱状图图表,通过该图表我们可以直观地展示和分析数据。此外,我还将提供…...
HDMI协议
HDMI设计3--HDMI 1.4/2.0 Transmitter Subsystem IP - 皮皮祥 - 博客园 HDMI设计4--HDMI 1.4/2.0 Receiver Subsystem IP - 皮皮祥 - 博客园 HDMI协议 - 标签 - 皮皮祥 - 博客园...
SpringBoot集成Flowable
一、工作流介绍 1、概念 通过计算机对业务流程的自动化管理。工作流是建立在业务流程的基础上,一个软件的系统核心根本上还是系统的业务流程,工作流只是协助进行业务流程管理。 解决的是:在多个参与者之间按照某种预定义的规则自动进行传递文…...
五,[GXYCTF2019]Ping Ping Ping1
进入靶场,有提示 我们在url试着输入本地IP,返回了ping命令 既然要在url处传参,那就用postman,再输入ip127.0.0.1 & ls,试着列出目录内容 ok,好像是个脏话,它过滤了空格 试着穿越又看到了脏话࿰…...