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

贪心算法简单介绍

贪心算法是一种在每一步选择中都采取当前状态下最优或最优近似的选择,以期望最终得到全局最优解的算法。贪心算法并不总能得到全局最优解,但在某些问题上,它可以得到全局最优解,并且比动态规划等其他方法更为简单和高效。

贪心算法的基本思想

贪心算法的核心思想是:

  1. 贪心选择性质:每一步都做出局部最优选择,即当前最优的选择,希望通过一系列局部最优选择能得到全局最优解。
  2. 无后效性:当前的选择不会影响后续的选择,即后面的选择不依赖于之前的状态。

贪心算法的应用场景

贪心算法通常用于解决一些优化问题,比如最短路径问题、背包问题、活动选择问题、最小生成树等。下面通过几个经典问题来介绍贪心算法。

1. 活动选择问题

问题描述

给定一组活动,每个活动有一个开始时间和结束时间。要求选择尽可能多的活动,使得这些活动互不冲突。

贪心策略

每次选择结束时间最早且不与已选活动冲突的活动。

代码实现
import java.util.Arrays;
import java.util.Comparator;public class ActivitySelection {static class Activity {int start, end;Activity(int start, int end) {this.start = start;this.end = end;}}public static void main(String[] args) {Activity[] activities = {new Activity(1, 4),new Activity(3, 5),new Activity(0, 6),new Activity(5, 7),new Activity(3, 9),new Activity(5, 9),new Activity(6, 10),new Activity(8, 11),new Activity(8, 12),new Activity(2, 14),new Activity(12, 16)};Arrays.sort(activities, Comparator.comparingInt(a -> a.end));int count = 1;int endTime = activities[0].end;for (int i = 1; i < activities.length; i++) {if (activities[i].start >= endTime) {count++;endTime = activities[i].end;}}System.out.println("Maximum number of activities: " + count);}
}

2. 0/1 背包问题的贪心近似

问题描述

给定一个容量为 W 的背包和 N 个物品,每个物品有一个重量和价值。要求在不超过背包容量的情况下,选择若干物品使得这些物品的总价值最大。

贪心策略

按单位价值(价值/重量)从大到小的顺序选择物品,尽量多地选择高单位价值的物品。

代码实现
import java.util.Arrays;
import java.util.Comparator;public class FractionalKnapsack {static class Item {int weight;int value;Item(int weight, int value) {this.weight = weight;this.value = value;}}public static void main(String[] args) {Item[] items = {new Item(10, 60),new Item(20, 100),new Item(30, 120)};int capacity = 50;Arrays.sort(items, Comparator.comparingDouble(i -> (double) i.value / i.weight).reversed());double totalValue = 0;int remainingCapacity = capacity;for (Item item : items) {if (item.weight <= remainingCapacity) {totalValue += item.value;remainingCapacity -= item.weight;} else {totalValue += item.value * ((double) remainingCapacity / item.weight);break;}}System.out.println("Maximum value in Knapsack = " + totalValue);}
}

3. 哈夫曼编码

问题描述

给定一组字符及其出现的频率,要求构建一棵二叉树,使得树的带权路径长度最小。带权路径长度是所有叶子节点的深度乘以频率之和。

贪心策略

每次选择频率最小的两个节点合并,直到所有节点合并成一棵树。

代码实现
import java.util.PriorityQueue;public class HuffmanCoding {static class Node {int freq;Node left, right;Node(int freq) {this.freq = freq;}}public static void main(String[] args) {int[] frequencies = {5, 9, 12, 13, 16, 45};PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.freq));for (int freq : frequencies) {pq.add(new Node(freq));}while (pq.size() > 1) {Node left = pq.poll();Node right = pq.poll();Node merged = new Node(left.freq + right.freq);merged.left = left;merged.right = right;pq.add(merged);}printCodes(pq.poll(), "");}private static void printCodes(Node root, String code) {if (root.left == null && root.right == null) {System.out.println(root.freq + ": " + code);return;}printCodes(root.left, code + "0");printCodes(root.right, code + "1");}
}

贪心算法的总结

贪心算法通过在每一步选择中都采取局部最优的选择,希望最终得到全局最优解。它通常用于解决一些优化问题,如活动选择问题、背包问题和哈夫曼编码等。虽然贪心算法不总能得到全局最优解,但在某些特定问题上,它能以简单和高效的方式得到全局最优解。理解贪心算法的基本思想和应用场景,有助于在实际问题中选择合适的算法解决方案。

相关文章:

贪心算法简单介绍

贪心算法是一种在每一步选择中都采取当前状态下最优或最优近似的选择&#xff0c;以期望最终得到全局最优解的算法。贪心算法并不总能得到全局最优解&#xff0c;但在某些问题上&#xff0c;它可以得到全局最优解&#xff0c;并且比动态规划等其他方法更为简单和高效。 贪心算…...

眼底项目经验

眼底项目经验 可解释性不足问题眼底项目有多牛逼可解释性不足解法数据、算力、算法都免费送不仅预测当下&#xff0c;还能预测未来和慢病管理整合&#xff0c;形成一个实时健康检测生态 可解释性不足问题 今天下午和腾讯眼底项目人员讨论, 他们不准备做全身性的多疾种, 因为深…...

使用arco design实现动态列信息的表格

目录 1.说明 2.普通表格的实现 3.动态表格的实现 1.说明 在前端画面中&#xff0c;表格一般用来展示列表数据&#xff0c;并且可以实现分页&#xff0c;应用很广泛&#xff0c;关于表格的列信息&#xff0c;一般是固定的&#xff0c;也可以是变化的&#xff0c;根据后端传递…...

解决 fatal: Not a git repository (or any of the parent directories): .git 问题

解决方法&#xff1a;在命令行 输入 git init 然后回车就好了...

Spring 模拟管理Web应用程序

MVC&#xff1a;Model View Controller 1&#xff09;controller&#xff1a;控制层&#xff08;Servlet是运行服务器端&#xff0c;处理请求响应java语言编写技术&#xff09; 2&#xff09;service&#xff1a;业务层&#xff08;事务&#xff0c;异常&#xff09; 3&#xf…...

修改了vue3 <script setup>留言板

Лунная ночь <template><button class"edit_view_checkbox"><input type"checkbox" v-model"editshowInput" value"编辑" /></button><div class"editshowInput" v-if"editshowI…...

jQuery 常用API

一、jQuery 选择器 1、jQuery 基础选择器 原生JS获取元素方式很多&#xff0c;很杂&#xff0c;而且兼容性情况不一致&#xff0c;因此jQuery给我们做了封装&#xff0c;使获取元素统一标准 2、jQuery 层级选择器 3、隐式迭代 遍历内部 DOM 元素&#xff08;伪数组形式存储&am…...

内网安全-隧道搭建穿透上线内网穿透-nps自定义上线内网渗透-Linux上线-cs上线Linux主机

目录 内网安全-隧道搭建&穿透上线内网穿透-nps-自定义-上线NPS工具介绍搭建过程 nps原理介绍MSF上线CS上线 内网渗透-Linux上线-cs上线Linux主机1.下载插件2.导入插件模块3.配置监听器4.服务端配置5.配置C2监听器并生成木马6.执行木马 内网安全-隧道搭建&穿透上线 内网…...

【AHK V2】设计模式之命令模式

目录 情景剧场什么是命令模式优缺点优点缺点 使用命令模式的步骤命令模式代码示例合理使用AI工具自动生成代码 情景剧场 我们来设想一个场景&#xff1a; 你进入一家餐馆&#xff0c;餐馆只有老板一个人&#xff08;老板即厨师&#xff09;。 “老板&#xff0c;一份小炒肉&am…...

2024年5月20日 (周二) 叶子游戏新闻

《边境之塔》登陆Steam 复古风恐怖生存冒险DascuMaru制作并发行&#xff0c;一款低像素3D复古风恐怖生存冒险新游《边境之塔&#xff08;The Tower on the Borderland&#xff09;》登陆Steam正式推出&#xff0c;限时九折优惠&#xff0c;本作暂不支持中文。 勇魅出击&#xf…...

【SQL学习进阶】从入门到高级应用(二)

文章目录 简单查询查一个字段查多个字段查所有字段查询时字段可参与数学运算查询时字段可起别名as关键字省略as关键字别名中有空格别名中有中文 &#x1f308;你好呀&#xff01;我是 山顶风景独好 &#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xf…...

FL Studio v21.2.3.4004中文破解版百度网盘下载

FL Studio v21.2.3.4004中文破解版是一款完整的软件音乐制作环境或数字音频工作站 (DAW)。代表了超过 18 年的创新发展&#xff0c;它在一个软件包中提供了您创作、编曲、录制、编辑、混音和掌握专业品质音乐所需的一切。FL Studio v21.2.3.4004中文破解版现在是世界上最受欢迎…...

从0开始写一个环境保护网站的第3天(JAVAWEB)

1.目标 实现首页的环境保护原因的查询&#xff0c;和底部友情连接部分 2.实现 2.1建立数据库表格&#xff08;这里数据全是百度查询&#xff09; 环境保护原因表&#xff1a; 友情连接表&#xff1a;&#xff08;数据来源https://zhuanlan.zhihu.com/p/696243646&#xff0…...

Java中volatile关键字

保证了不同线程对这个变量进行操作时的可见性&#xff0c;即一个线程修改了某个变量的值&#xff0c;这新值对其他线程来说是立即可见的,volatile关键字会强制将修改的值立即写入主存。 1.volatile的可见性 一个典型的例子&#xff1a;永不停止的循环。 public class Forever…...

医院挂号就诊系统的设计与实现

前端使用Vue.js 后端使用SpiringBoot MyBatis 数据使用MySQL 需要项目和论文加企鹅&#xff1a;2583550535 医院挂号就诊系统的设计与实现_哔哩哔哩_bilibili 随着社会的发展&#xff0c;医疗资源分布不均&#xff0c;患者就诊难、排队时间长等问题日益突出&#xff0c;传统的…...

SpringBoot整合RabbitMQ的快速使用教程

目录 一、引入依赖 二、配置rabbitmq的连接信息等 1、生产者配置 2、消费者配置 三、设置消息转换器 四、生产者代码示例 1、配置交换机和队列信息 2、生产消息代码 五、消费者代码示例 1、消费层代码 2、业务层代码 在分布式系统中&#xff0c;消息队列是一种重要…...

pytorch比较操作

文章目录 常用的比较操作1.torch.allclose()2.torch.argsort()3.torch.eq()4.torch.equal()5.torch.greater_equal()6.torch.gt()7.torch.isclose()8.torch.isfinite()9.torch.isif()10.torch.isposinf()11.torch.isneginf()12.torch.isnan()13.torch.kthvalue()14.torch.less_…...

2024年4月—马克思主义基本原理概论真题及答案解析(上海自考)

目录 1.选择题 2.简答题 3.论述题 1.选择题 2.简答题...

「Element-UI表头添加带Icon的提示信息」

一、封装全局组件 &#x1f353; 注意&#xff1a;可以直接复制该文件 <!-- // 写一个PromptMessage的组件&#xff0c;并全局注册 --> <template><div class"tooltip"><el-tooltip effect"dark" placement"right">&l…...

单细胞 10X 和seurat对象学习

单细胞seurat数据的基础知识 rm(list ls()) library(Seurat) #注意这个报错 #Warning: Feature names cannot have underscores (_), replacing with dashes (-) folderslist.files(./,pattern[123]$) folders scList lapply(folders,function(folder){ CreateSeuratObject(…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...