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

算法--贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤其有效,这意味着局部最优解能决定全局最优解。简单来说,贪心算法对每个子问题都做出选择,不能回退,这与动态规划不同,后者会保存以前的结果,并根据以前的结果对当前进行选择,有回退功能。

贪心算法的特点:

  1. 局部最优选择:在每一步都做出在当前看来最优的选择,希望这些局部最优能导致全局最优解。
  2. 无回退操作:一旦做出了选择,就不再回退,即不考虑以前的选择。

贪心算法适用的问题:
贪心算法适用于具有“贪心选择性质”的问题,即局部最优解能决定全局最优解。贪心算法不能保证求得的最后解是最佳的,也不能用来求最大或最小解的问题,只能求满足某些约束条件的可行解的范围。

贪心算法的应用实例包括:

  • 找零问题:如何用最少的硬币找零。
  • 最小生成树:如Kruskal算法和Prim算法。
  • 单源最短路径:如Dijkstra算法。
  • 任务调度问题:如何安排任务以减少等待时间或延迟。
  • 压缩编码:如Huffman编码。

贪心算法的设计步骤:

  1. 建立数学模型来描述问题。
  2. 把求解的问题分成若干个子问题。
  3. 对每一子问题求解,得到子问题的局部最优解。
  4. 把子问题的解局部最优解合成原来解问题的一个解。

虽然贪心算法相对简单易懂,但它并不总是能得到全局最优解,因此在使用时需要仔细分析问题是否适合采用贪心算法。

贪心算法可以用来解决背包问题的一种特殊形式——分数背包问题(Fractional Knapsack Problem),但对于经典的0-1背包问题,贪心算法通常无法保证找到最优解。

分数背包问题
在分数背包问题中,你可以将物品分割成任意大小,然后选择其中的一部分放入背包中,目标是最大化背包中物品的总价值,同时不超过背包的容量限制。对于这个问题,贪心算法是有效的,因为你可以按照物品的价值重量比(单位价值)来选择物品,优先选择单位价值最高的物品,直到背包装满为止。

0-1背包问题
对于0-1背包问题,每个物品只能整体选取或不选取,不能分割。这种情况下,贪心算法选择物品的策略可能无法得到最优解。例如,如果贪心算法只考虑物品的价值或重量,而不是价值重量比,那么它可能会错过更优的组合,因为一个轻而价值高的物品可能比几个重而价值低的物品更有价值。

对于0-1背包问题,最优解可能需要通过动态规划等方法来找到,因为贪心算法可能无法考虑到所有物品组合的总价值。
总结,贪心算法适用于分数背包问题,但对于0-1背包问题,它可能无法保证找到最优解。

以下是使用贪心算法解决分数背包问题的C语言实现。在这个实现中,我们首先根据物品的价值重量比(单位价值)对物品进行排序,然后按单位价值从高到低依次选择物品放入背包,直到背包容量达到限制。

#include <stdio.h>
#include <stdlib.h>// 定义物品结构体
typedef struct {float weight; // 物品重量float value;  // 物品价值float ratio;  // 价值重量比
} Item;// 比较函数,用于排序
int compare(const void *s1, const void *s2) {Item *e1 = (Item *)s1;Item *e2 = (Item *)s2;return e2->ratio - e1->ratio > 0 ? 1 : -1; // 降序排序
}// 贪心算法解决分数背包问题
float fractionalKnapsack(int W, Item arr[], int n) {// 按价值重量比排序qsort(arr, n, sizeof(arr[0]), compare);int curWeight = 0;  // 当前背包重量float finalvalue = 0.0; // 结果(总价值)// 遍历所有物品for (int i = 0; i < n; i++) {// 如果加入当前物品不超过最大重量,加入整个物品if (curWeight + arr[i].weight <= W) {curWeight += arr[i].weight;finalvalue += arr[i].value;} else {// 如果不能加入整个物品,加入背包能装下的部分int remain = W - curWeight;finalvalue += arr[i].value * ((float) remain / arr[i].weight);break; // 背包已满}}return finalvalue;
}// 测试代码
int main() {int W = 50;  // 背包容量Item arr[] = {{10, 60}, {20, 100}, {30, 120}};int n = sizeof(arr) / sizeof(arr[0]);printf("最大价值为: %.2f", fractionalKnapsack(W, arr, n));return 0;
}

这段代码首先定义了一个Item结构体来存储每个物品的重量、价值和价值重量比。compare函数用于根据价值重量比对物品进行降序排序。fractionalKnapsack函数实现了贪心算法,首先对物品按价值重量比进行排序,然后遍历排序后的物品数组,根据背包剩余容量决定是否将当前物品整个或部分加入背包。最后,函数返回背包中物品的最大总价值。

相关文章:

算法--贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优&#xff08;即最有利&#xff09;的选择&#xff0c;从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤其有效&#xff0c;这意味着局部最优解能决定全局最优解。简单来说&#xff0c;贪心…...

Redis基本數據結構 ― String

Redis基本數據結構 ― String 介紹常用命令範例1. 為字串鍵設值/取得字串鍵的值2. 查看字串鍵的過期時間3. 如何為key設置時間?4. 如何刪除指定key?5. 如何增加value的值?6. 獲取value值的長度 介紹 字串鍵是Redis中最基本的鍵值對類型&#xff0c;這種類型的鍵值對會在數據…...

php7.4在foreach中对使用数据使用无法??[]判读,无法使用引用传递

代码如下图&#xff1a;这样子在foreach中是无法修改class_history的。正确的应该是去掉??[]判断。 public function actionY(){$array [name>aaa,class_history>[[class_name>一班,class_num>1],[class_name>二班,class_num>2]]];foreach ($array[class_…...

传输层协议 TCP UDP协议 解析(二)

文章目录 UDP&#xff1a;用户数据报协议UDP报文格式TCP与UDP的区别 UDP&#xff1a;用户数据报协议 UDP是一种面向无连接的传输层协议&#xff08;数据一直发送&#xff0c;没有ack&#xff0c;所以不需要考虑ack&#xff09;&#xff0c;传输可靠性没有保证。 UDP不提供重传…...

java+jsp+Oracle+Tomcat 记账管理系统论文(一)

⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️ ➡️点击免费下载全套资料:源码、数据库、部署教程、论文、答辩ppt一条龙服务 ➡️有部署问题可私信联系 ⬆️⬆️⬆️​​​​​​​⬆️…...

echarts双Y轴,并实现图例等

一个Y轴时yAxis为对象 yAxis: {type: value,name: 占比(%) },两个Y轴时yAxis为数组 yAxis: [{ // 左侧的type: value,name: 占比(%),nameTextStyle: {padding: [0, 0, 10, -50]},min: 0,max: 100,splitNumber: this.splitNumber, // 设置坐标轴的分割段数interval: 20, // 标轴…...

STM32 工程移植 LVGL:一步一步完成

STM32 工程移植 LVGL&#xff1a;一步一步完成 LVGL&#xff0c;作为一款强大且灵活的开源图形库&#xff0c;专为嵌入式系统GUI设计而生&#xff0c;极大地简化了开发者在创建美观用户界面时的工作。作为一名初学者&#xff0c;小编正逐步深入探索LVGL的奥秘&#xff0c;并决…...

Linux中分析日志及问题排查

可以参考:Linux命令 Linux系统日志是系统管理和故障排查的关键工具。通过分析系统日志,我们能够深入了解系统的运行状况,迅速发现并解决潜在的问题。 1. 日志文件位置 系统日志通常存储在/var/log/目录下,不同的日志有不同的文件,如下: /var/log/syslog:系统日志,包含…...

复杂环境下实时鲁棒3D激光雷达定位

复杂环境下实时鲁棒3D激光雷达定位 一、摘要 定位是机器人领域的重要研究方向。本篇文章里&#xff0c;我们提出了一种基于3D激光雷达的复杂环境下的定位方案。我们首先使用GPS和雷达建立一张点云地图&#xff0c;然后在匹配定位的时候从大地图中分割出一个小地图&#xff0c…...

9.3.k8s的控制器资源(deployment部署控制器)

目录 一、deployment部署控制器概念 二、deployment资源的清单编写 三、小结 功能 使用场景 原理 四、deployment实现升级和回滚 1.编辑deployment资源清单&#xff08;v1版本&#xff09; 2.创建service资源用于访问 ​编辑 3.修改deploy清单中pod镜像版本为V2 4…...

通过符号程序搜索提升prompt工程

原文地址&#xff1a;supercharging-prompt-engineering-via-symbolic-program-search 通过自动探索​​大量提示变体来找到更好的提示 2024 年 4 月 22 日 众所周知&#xff0c;LLMs的成功在很大程度上仍然取决于我们用正确的指导和例子来提示他们的能力。随着新一代LLMs变得越…...

js开启子线程及其使用

众所周知&#xff0c;js是单线程&#xff0c;但是可以开启子线程来帮忙处理一些数据&#xff0c;但是这个子线程是有限制的 1.必须是同源 2.完全受主线程控制 3.不能在子线程中操作dom节点 4.子线程没有window&#xff0c;可以使用self 5.等等 具体的查看官网 进程切换是要耗时…...

excel办公系列-图表元素及其作用

Excel图表元素及其作用 Excel图表由各种元素组成&#xff0c;每个元素都有其特定的作用&#xff0c;可以帮助我们更清晰地传达数据信息。下面将介绍Excel图表中常见的一些元素及其作用&#xff0c;并附上相关截图。 原始数据 月份 网站访问量 (万次&#xff09; 销售额 (万…...

rocketmq dashboard控制台中topic状态无法展示

现象 在使用rocketmq控制台查看topic状态和订阅状态时&#xff0c;出现错误和没有信息的情况。 原因 rocketmq控制台版本问题&#xff0c;最新版本为1.0.1&#xff0c;支持rocketmq5版本&#xff0c;如果使用rocketmq4版本的服务无法兼容对应的数据。同理1.0.0版本也无法兼容ro…...

GPT每日面试题-Typescript中type和interface的区别

充分利用ChatGPT的优势&#xff0c;帮助我们快速准备前端面试。今日问题&#xff1a;typescript中type和interface的区别? Q&#xff1a;如果在前端面试中&#xff0c;被问到typescript的type和interface的区别是什么&#xff0c;怎么回答最好&#xff1f; A&#xff1a;当谈…...

python数据分析——大数据伦理风险分析

大数据伦理风险分析 前言一、大数据伦理二、大数据技术伦理风险2.1算法安全性、可信赖性及稳定性风险及其应对2.2算法的可解释性风险及其应对2.3算法的决策不可预见性风险及其应对2.4数据收集与储存中的泄漏风险及其应对2.5案例&#xff1a;某大型电商平台内部员工涉嫌窃取50亿…...

配置 Trunk,实现相同VLAN的跨交换机通信

1.实验环境 公司的员工人数已达到 100 人&#xff0c;其网络设备如图所示。现在的网络环境导致广播较多网速慢&#xff0c;并且也不安全。公司希望按照部门划分网络&#xff0c;并且能够保证一定的网络安全性。 其网络规划如下。 PC1和 PC3为财务部&#xff0c;属于VLAN 2&…...

Python 植物大战僵尸

文章目录 效果图项目结构实现思路源代码 效果图 项目结构 实现思路 下面是代码的实现思路&#xff1a; 导入必要的库和模块&#xff1a;首先&#xff0c;我们导入了Python的os、time库以及pygame库&#xff0c;还有植物大战僵尸游戏中用到的各个植物和僵尸的类。 初始化游戏和…...

SpringBoot:实战项目TLIAS智能学习辅助系统1.1

SpringBootWeb项目 TILAS智能学习辅助系统 需求 部门管理 查询部门列表 删除部门 新增部门 修改部门 员工管理 查询员工列表(分页) 删除员工 新增员工 修改员工 准备工作 导入依赖 web(2.7.6) mybatis mysql驱动 lombok 准备好包结构 Controller->Servi…...

ubuntu-meta-22.04桌面版+ros2-humble 镜像

ubuntu-meta-22.04桌面版ros2-humble 镜像 下载地址&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1PSBe4EqWch44OQUlkCCEig?pwdknty 提取码&#xff1a;knty 镜像文件较大&#xff0c;分成了两个压缩包&#xff0c;下载后直接解压ubuntu22.04-desk-meta-ros2-arm (…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...