算法--贪心算法
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤其有效,这意味着局部最优解能决定全局最优解。简单来说,贪心算法对每个子问题都做出选择,不能回退,这与动态规划不同,后者会保存以前的结果,并根据以前的结果对当前进行选择,有回退功能。
贪心算法的特点:
- 局部最优选择:在每一步都做出在当前看来最优的选择,希望这些局部最优能导致全局最优解。
- 无回退操作:一旦做出了选择,就不再回退,即不考虑以前的选择。
贪心算法适用的问题:
贪心算法适用于具有“贪心选择性质”的问题,即局部最优解能决定全局最优解。贪心算法不能保证求得的最后解是最佳的,也不能用来求最大或最小解的问题,只能求满足某些约束条件的可行解的范围。
贪心算法的应用实例包括:
- 找零问题:如何用最少的硬币找零。
- 最小生成树:如Kruskal算法和Prim算法。
- 单源最短路径:如Dijkstra算法。
- 任务调度问题:如何安排任务以减少等待时间或延迟。
- 压缩编码:如Huffman编码。
贪心算法的设计步骤:
- 建立数学模型来描述问题。
- 把求解的问题分成若干个子问题。
- 对每一子问题求解,得到子问题的局部最优解。
- 把子问题的解局部最优解合成原来解问题的一个解。
虽然贪心算法相对简单易懂,但它并不总是能得到全局最优解,因此在使用时需要仔细分析问题是否适合采用贪心算法。
贪心算法可以用来解决背包问题的一种特殊形式——分数背包问题(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函数实现了贪心算法,首先对物品按价值重量比进行排序,然后遍历排序后的物品数组,根据背包剩余容量决定是否将当前物品整个或部分加入背包。最后,函数返回背包中物品的最大总价值。
相关文章:
算法--贪心算法
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤其有效,这意味着局部最优解能决定全局最优解。简单来说,贪心…...

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

php7.4在foreach中对使用数据使用无法??[]判读,无法使用引用传递
代码如下图:这样子在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:用户数据报协议UDP报文格式TCP与UDP的区别 UDP:用户数据报协议 UDP是一种面向无连接的传输层协议(数据一直发送,没有ack,所以不需要考虑ack),传输可靠性没有保证。 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:一步一步完成 LVGL,作为一款强大且灵活的开源图形库,专为嵌入式系统GUI设计而生,极大地简化了开发者在创建美观用户界面时的工作。作为一名初学者,小编正逐步深入探索LVGL的奥秘,并决…...
Linux中分析日志及问题排查
可以参考:Linux命令 Linux系统日志是系统管理和故障排查的关键工具。通过分析系统日志,我们能够深入了解系统的运行状况,迅速发现并解决潜在的问题。 1. 日志文件位置 系统日志通常存储在/var/log/目录下,不同的日志有不同的文件,如下: /var/log/syslog:系统日志,包含…...

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

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

通过符号程序搜索提升prompt工程
原文地址:supercharging-prompt-engineering-via-symbolic-program-search 通过自动探索大量提示变体来找到更好的提示 2024 年 4 月 22 日 众所周知,LLMs的成功在很大程度上仍然取决于我们用正确的指导和例子来提示他们的能力。随着新一代LLMs变得越…...
js开启子线程及其使用
众所周知,js是单线程,但是可以开启子线程来帮忙处理一些数据,但是这个子线程是有限制的 1.必须是同源 2.完全受主线程控制 3.不能在子线程中操作dom节点 4.子线程没有window,可以使用self 5.等等 具体的查看官网 进程切换是要耗时…...

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

rocketmq dashboard控制台中topic状态无法展示
现象 在使用rocketmq控制台查看topic状态和订阅状态时,出现错误和没有信息的情况。 原因 rocketmq控制台版本问题,最新版本为1.0.1,支持rocketmq5版本,如果使用rocketmq4版本的服务无法兼容对应的数据。同理1.0.0版本也无法兼容ro…...
GPT每日面试题-Typescript中type和interface的区别
充分利用ChatGPT的优势,帮助我们快速准备前端面试。今日问题:typescript中type和interface的区别? Q:如果在前端面试中,被问到typescript的type和interface的区别是什么,怎么回答最好? A:当谈…...
python数据分析——大数据伦理风险分析
大数据伦理风险分析 前言一、大数据伦理二、大数据技术伦理风险2.1算法安全性、可信赖性及稳定性风险及其应对2.2算法的可解释性风险及其应对2.3算法的决策不可预见性风险及其应对2.4数据收集与储存中的泄漏风险及其应对2.5案例:某大型电商平台内部员工涉嫌窃取50亿…...

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

Python 植物大战僵尸
文章目录 效果图项目结构实现思路源代码 效果图 项目结构 实现思路 下面是代码的实现思路: 导入必要的库和模块:首先,我们导入了Python的os、time库以及pygame库,还有植物大战僵尸游戏中用到的各个植物和僵尸的类。 初始化游戏和…...
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 镜像 下载地址: 链接:https://pan.baidu.com/s/1PSBe4EqWch44OQUlkCCEig?pwdknty 提取码:knty 镜像文件较大,分成了两个压缩包,下载后直接解压ubuntu22.04-desk-meta-ros2-arm (…...

IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...

AD学习(3)
1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分: (1)PCB焊盘:表层的铜 ,top层的铜 (2)管脚序号:用来关联原理图中的管脚的序号,原理图的序号需要和PCB封装一一…...