贪心算法详细讲解(沉淀中)

devtools/2025/1/16 23:26:37/

文章目录

  • 1. 什么是算法>贪心算法?(贪婪+鼠目寸光)
    • 经典例题
      • 1.1.1 找零问题
      • 1.1.2最小路径和
      • 1.1.3 背包问题
  • 2.算法>贪心算法的特点
    • 2.1 证明例1
  • 3.学习贪心的方向
  • 心得体会

1. 什么是算法>贪心算法?(贪婪+鼠目寸光)

贪心策略:解决问题的策略局部优先 -> 全局优先
贪心策略:
1.把解决问题的过程分为若干步;
2.解决每一步的时候,都选择当前看起来“最优的”解法;
3.“希望”得到全局最优解。

经典例题

1.1.1 找零问题

在这里插入图片描述

1.1.2最小路径和

在这里插入图片描述

1.1.3 背包问题

在这里插入图片描述

2.算法>贪心算法的特点

(1)贪心策略到的提出
1.贪心策略的提出是没有标准及模板的。
2.可能每一道题的贪心策略都是不同的
(2)贪心策略的正确性
因为有可能“贪心策略”是一个错误的方法;
正确的贪心策略,我们是需要“证明的”。
常用的证明方法:数学中见过的所有证明方法。
eg:
1.错误的比较好证明,在例2,3中:
例2:
在这里插入图片描述

绿色路径和:1+3+1+1+1=7,比10小,所以这里的贪心策略是错误的。
例三:
在这里插入图片描述

这里用2个2号,价值是14 ,比13 大,所以这里的贪心策略是错误的。

2.1 证明例1

在这里插入图片描述

3.学习贪心的方向

遇到不会的题放平心态。
1.前期学习的时候,把重点放在贪心的策略上,把这个策略当成经验吸收。
2.如何去证明?

心得体会

以上内容就是算法>贪心算法的重点内容,如果想深入学习,那就多做练习,学习不同的关于算法>贪心算法的习题,提升自己。喜欢博主的,可以一键三连,支持博主!!!!


http://www.ppmy.cn/devtools/151098.html

相关文章

计算机组成原理简答题、名词解释整理(考研、期末)

第一章 计算机系统的概论 计算机系统由硬件和软件两大部分组成一。 硬件,是指计算机的实体部分,他由看的见摸得着的各种电子元器件,各类光电机设备的实物组成,如主机、外部设备。 软件,指人们事先编制的具有各类特殊…

iOS - 底层实现中涉及的类型

1. 基本类型定义 // 基础类型 typedef unsigned long uintptr_t; // 指针大小的无符号整数 typedef long ptrdiff_t; // 指针差值类型 typedef unsigned int uint32_t; // 32位无符号整数 typedef unsigned long long uint64_t; // 64…

C语言-数据结构-队列

目录 1.队列的特点 2.队列的实现 2.1.初始化队列 2.2.入队列 2.2.1.入空队列 2.2.2.入非空队列 2.3.出队列 2.4.销毁队列 2.5.完整代码 3.实际应用 1.队列的特点 队列是一种常见的数据结构,它遵循先进先出(FIFO, First In First Out&#xff09…

electron编写一个macOS风格的桌面应用

electron编写一个macOS风格的桌面应用 基于vue3vite,看一下最后的效果: 针对原始的electron模板,做了如下几点调整: 背景边框进行了圆角处理隐藏了原始的titleBar增加了macOS风格的窗口管理工具,就是交通灯按钮组实现…

api开发及运用小红书笔记详情api如何获取笔记详情信息

item_get_video-获得某书笔记详情 smallredbook.item_get_video 公共参数 名称类型必须描述keyString是调用key(必须以GET方式拼接在URL中)secretString是调用密钥api_nameString是API接口名称(包括在请求地址中)[item_search,i…

RPC 源码解析~Apache Dubbo

解析 RPC(远程过程调用)的源码可以帮助你深入理解其工作原理和实现细节。为了更好地进行源码解析,我们选择一个流行的 RPC 框架——Apache Dubbo 作为示例。Dubbo 是一个高性能、轻量级的开源 Java RPC 框架,广泛应用于企业级应用…

机器学习在服务监控中的创新应用:提升运维效率与可靠性

《机器学习在服务监控中的创新应用:提升运维效率与可靠性》 一、引言 在当今复杂的信息技术环境中,服务监控对于确保系统的稳定运行至关重要。传统的服务监控方法往往依赖于预定义的阈值和规则,但在面对复杂多变的服务行为时,这些方法可能会显得力不从心。机器学习的出现…

AI知识-TF-IDF技术(Term Frequency-Inverse Document Frequency)

摘要 TF-IDF(Term Frequency-Inverse Document Frequency)是一种常见的统计方法,用于评估一个词对于一个文档集或一个语料库中的其中一份文档的重要性。本文将全面阐述TF-IDF的通俗理解、技术原理、应用场景,并做以总结。 通俗理…