C#贪心算法
贪心算法:生活与代码中的 “最优选择大师”
在生活里,我们常常面临各种选择,都希望能做出最有利的决策。比如在超市大促销时,面对琳琅满目的商品,你总想用有限的预算买到价值最高的东西。贪心算法,就像是一个精明的生活顾问,总能在每一步都做出当下看起来最优的选择,帮我们在各种场景中找到 “最优解”。
贪心算法原理:目光短浅却很高效
贪心算法遵循一种 “今朝有酒今朝醉” 的策略,在对问题求解时,总是做出在当前看来是最好的选择。它并不从整体最优上加以考虑,所做出的仅仅是在某种意义上的局部最优解。但神奇的是,在很多情况下,这些局部最优解最后能构成全局最优解。
想象你在一个布满金币的房间,规定只能拿一次,每次拿一枚。贪心算法会让你在每一次伸手时,都选择眼前最大的那枚金币,而不考虑未来可能出现更大金币的情况。虽然看起来有点 “目光短浅”,但在合适的问题中,这种策略能高效地解决问题。

应用场景及代码实现
活动安排问题:时间管理大师的秘诀
假设你是一个忙碌的职场人,一天内有多个会议要参加,每个会议都有开始时间和结束时间,你想参加尽可能多的会议,该怎么选择呢?这就是活动安排问题。
贪心算法的策略是:优先选择结束时间最早的会议,只要这个会议的开始时间晚于前一个已选择会议的结束时间,就把它加入日程。
using System;
using System.Collections.Generic;
using System.Linq;
class Activity
{public int Start { get; set; }public int End { get; set; }public Activity(int start, int end){Start = start;End = end;}
}class GreedyAlgorithm
{public static List<Activity> ActivitySelection(List<Activity> activities){activities = activities.OrderBy(a => a.End).ToList();List<Activity> selectedActivities = new List<Activity>();selectedActivities.Add(activities[0]);int lastEnd = activities[0].End;for (int i = 1; i < activities.Count; i++){if (activities[i].Start >= lastEnd){selectedActivities.Add(activities[i]);lastEnd = activities[i].End;}}return selectedActivities;}
}class Program
{static void Main(){List<Activity> activities = new List<Activity>{new Activity(1, 3),new Activity(2, 5),new Activity(4, 6),new Activity(5, 7),new Activity(7, 9)};List<Activity> selected = GreedyAlgorithm.ActivitySelection(activities);Console.WriteLine("选择的活动:");foreach (var activity in selected){Console.WriteLine($"开始时间: {activity.Start}, 结束时间: {activity.End}");}}
}
找零问题:收银员的高效策略
当你去商店购物付款后,收银员需要找给你零钱。假设商店有各种面额的硬币和纸币,如何用最少的货币数量找零呢?
贪心算法的做法是:每次都优先选择面额最大的货币,直到找零金额为零。
using System;
using System.Collections.Generic;
class GreedyAlgorithm
{public static List<int> MakeChange(int amount, List<int> denominations){denominations = denominations.OrderByDescending(d => d).ToList();List<int> change = new List<int>();foreach (int denomination in denominations){while (amount >= denomination{amount -= denomination;change.Add(denomination);}}return change;}
}class Program
{static void Main(){int amount = 63;List<int> denominations = new List<int> { 25, 10, 5, 1 };List<int> change = GreedyAlgorithm.MakeChange(amount, denominations);Console.WriteLine("找零方案:");foreach (int coin in change){Console.Write(coin + " ");}}
}
背包问题(部分背包):灵活的背包打包法
在背包问题中,有一个容量有限的背包和一些物品,每个物品有重量和价值。部分背包问题允许你选择物品的一部分放入背包,目标是使背包内物品的总价值最大。
贪心算法的思路是:计算每个物品的价值重量比,优先选择价值重量比高的物品放入背包,直到背包装满。
using System;
using System.Collections.Generic;
using System.Linq;
class Item
{public int Weight { get; set; }public int Value { get; set; }public double ValuePerWeight => (double)Value / Weight;public Item(int weight, int value){Weight = weight;Value = value;}
}class GreedyAlgorithm
{public static double FractionalKnapsack(int capacity, List<Item> items){items = items.OrderByDescending(i => i.ValuePerWeight).ToList();double totalValue = 0;int currentWeight = 0;foreach (var item in items){if (currentWeight + item.Weight <= capacity){currentWeight += item.Weight;totalValue += item.Value;}else{int remainingCapacity = capacity - currentWeight;totalValue += item.ValuePerWeight * remainingCapacity;break;}}return totalValue;}
}class Program
{static void Main(){int capacity = 50;List<Item> items = new List<Item>{new Item(10, 60),new Item(20, 100),new Item(30, 120)};double maxValue = GreedyAlgorithm.FractionalKnapsack(capacity, items);Console.WriteLine($"背包能装下的最大价值: {maxValue}");}
}
贪心算法虽然在很多场景下表现出色,但它并非万能的。它的正确性依赖于问题本身具有的贪心选择性质和最优子结构性质。在实际应用中,需要仔细分析问题,判断贪心算法是否适用。要是你还想了解贪心算法在其他领域的应用,或者对代码实现有疑问,欢迎随时和我交流。
相关文章:
C#贪心算法
贪心算法:生活与代码中的 “最优选择大师” 在生活里,我们常常面临各种选择,都希望能做出最有利的决策。比如在超市大促销时,面对琳琅满目的商品,你总想用有限的预算买到价值最高的东西。贪心算法,就像是一…...
Vue程序下载
Vue是一个基于JavaScript(JS)实现的框架,想要使用它,就得先拿到Vue的js文件 Vue官网 Vue2:Vue.js Vue3:Vue.js - 渐进式 JavaScript 框架 | Vue.js 下载并安装vue.js 第一步:打开Vue2官网&a…...
【UCB CS 61B SP24】Lecture 17 - Data Structures 3: B-Trees学习笔记
本文以 2-3-4 树详细讲解了 B 树的概念,逐步分析其操作,并用 Java 实现了标准的 B 树。 1. 2-3 & 2-3-4 Trees 上一节课中讲到的二叉搜索树当数据是随机顺序插入的时候能够使得树变得比较茂密,如下图右侧所示,时间复杂度也就…...
机器学习决策树
一、香农公式 熵: 信息增益: 信息增益信息熵-条件熵 前者是初始信息熵大小,后者是因为条件加入后带来的确定性增加 信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度 信息增益越大说明影响越大 二、代码 ""&…...
Spring Boot + MyBatis 实现 RESTful API 的完整流程
后端开发:Spring Boot 快速开发实战 引言 在现代后端开发中,Spring Boot 因其轻量级、快速开发的特性而备受开发者青睐。本文将带你从零开始,使用 Spring Boot MyBatis 实现一个完整的 RESTful API,并深入探讨如何优雅地处理异…...
通过 ANSYS Discovery 进行 CFD 分析,增强工程设计
概括 工程师使用计算流体动力学 (CFD) 分析来研究和优化各种应用中的流体流动和传热分析。ANSYS Discovery 是一个用户友好的软件平台,使工程师能够轻松设置和解决 CFD 模型,并能够通知设计修改 在这篇博文中,我们将重点介绍在 Ansys Disc…...
家用可燃气体探测器——家庭燃气安全的坚实防线
随着社会的发展和变迁,天然气为我们的生活带来了诸多便利,无论是烹饪美食,还是温暖取暖,都离不开它的支持。然而,燃气安全隐患如影随形,一旦发生泄漏,可能引发爆炸、火灾等严重事故,…...
ListControl双击实现可编辑
为Edit Control控件添加丢失输入焦点事件,可见设为false 为List Control控件添加双击事件 控件和成员变量之间交换数据 CListCtrl ListPrint1; //列表输出 CEdit...
ave-form.vue 组件中 如何将产品名称发送给后端 ?
如何将产品名称发送给后端。 在这段代码中,产品名称(productName)的处理和发送主要发生在 save() 方法中。让我逐步分析: 产品ID的选择: <w-form-selectv-model"form.productId"label"涉及产品&q…...
DeepSeek行业应用实践报告-智灵动力【112页PPT全】
DeepSeek(深度搜索)近期引发广泛关注并成为众多企业/开发者争相接入的现象,主要源于其在技术突破、市场需求适配性及生态建设等方面的综合优势。以下是关键原因分析: 一、技术核心优势 开源与低成本 DeepSeek基于开源架构…...
【Markdown 语法简洁讲解】
Markdown 语法简洁语法讲解 什么是 Markdown1. 标题2. 列表3.文本样式4. 链接与图片5. 代码6. 表格7. 分割线8. 流程图9. 数学公式10. 快捷键11. 字体、字号与颜色 什么是 Markdown Markdown 是一种轻量级标记语言,通过简单的符号实现排版格式化,专注于…...
250301-OpenWebUI配置DeepSeek-火山方舟+硅基流动+联网搜索+推理显示
A. 最终效果 B. 火山方舟配置(一定要点击添加) C. 硅基流动配置(最好要点击添加,否则会自动弹出所有模型) D. 联网搜索配置 E. 推理过程显示 默认是没有下面的推理过程的显示的 设置步骤: 在Functions函…...
【3天快速入门WPF】12-MVVM
目录 1. 什么是MVVM2. 实现简单MVVM2.1. Part 12.2. Part 21. 什么是MVVM MVVM 是 Model-View-ViewModel 的缩写,是一种用于构建用户界面的设计模式,是一种简化用户界面的事件驱动编程方式。 MVVM 的目标是实现用户界面和业务逻辑之间的彻底分离,以便更好地管理和维护应用…...
查找Excel包含关键字的行(の几种简单快速方法)
需求:数据在后缀为xlsx的Excel的sheet1中且量比较大,比如几十万行几百列;想查找一个关键字所在的行,比如"全网首发"; 情况①知道关键字在哪一列 情况②不确定在哪一列,很多列相似又不同,本文演…...
性能测试分析和调优
步骤 性能调优的步骤 性能调优的步骤: 1.确定问题:根据性能测试的结果来分析确定bug。–测试人员职责 2.分析原因:分析问题产生的原因。----开发人员职责 3.给出解决方案:可以是修改软件配置、增加硬件资源配置、修改代码等----…...
(视频教程)Compass代谢分析详细流程及python版-R语言版下游分析和可视化
不想做太多的前情解说了,有点累了,做了很久的内容,包括整个分析,从软件安装和报错解决到后期下游python版-R语言版下游分析和可视化!单细胞代谢分析我们写过很多了,唯独少了最“高级”的compass,…...
【SQL】MySQL中的字符串处理函数:concat 函数拼接字符串,COALESCE函数处理NULL字符串
MySQL中的字符串处理函数:concat 函数 一、concat ()函数 1.1、基本语法1.2、示例1.3、特殊用途 二、COALESCE()函数 2.1、基本语法2.2、示例2.3、用途 三、进阶练习 3.1 条件和 SQL 语句3.2、解释 一、concat &…...
c++中深拷贝和浅拷贝的联系和区别
在 C 编程里,深拷贝和浅拷贝是两种不同的对象复制方式,它们在实现方式、资源管理和适用场景等方面存在显著差异。下面为你详细介绍它们的区别。 1. 基本概念 浅拷贝:浅拷贝仅仅复制对象的成员变量值。对于基本数据类型(如 int、d…...
Autotestplat 在多个平台和公司推荐使用!
1、 51Testing软件测试网 开源好用!推荐一款更轻量化的自动化测试平台! 2、程序员杨叔 从繁琐到简单!Autotestplat自动化测试平台搭建使用 3、一飞开源 [开源]一站式自动化测试平台及解决方案,支持接口、性能、UI测试 4、github h…...
字符串最后一个单词的长度
一:题目 二:思路 用rfind()函数倒着找第一个空格,返回的值为pos,然后打印size()-(pos1),posnpos就代表只有一个单词,则直接返回size #include <iostream> using namespace std; int main() {strin…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...
