首页 > 编程语言 >贪心算法

贪心算法

时间:2024-04-07 19:13:55浏览次数:25  
标签:int 孩子 问题 算法 区间 最优 贪心

1、基本概念

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,
从而希望导致结果是全局最好或最优的算法。

贪心算法解决问题的策略是:做出选择时,每次都选择对当前状态最优的解,而不考虑整个问题的解空间。它通常用来解决最优化问题,如最小生成树、哈夫曼编码等。

2、步骤

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

3、使用条件

利用贪心法求解的问题应具备如下2个特征:

1、贪心选择性质

一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次的选择可以依赖以前作出的选择,但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中,至于什么问题具有什么样的贪心选择性质是不确定的,需要具体问题具体分析。

局部最优解:观察问题是否可以通过选择当前看起来最优的解决方案来逐步构建全局最优解。

问题分解:分析问题是否可以分解成较小的子问题,且这些子问题的最优解能够直接用来构建原问题的最优解。

4、常见的贪心策略类型

  • 选择最大(或最小)元素:在解决一些优化问题时,优先选择当前最大或最小的元素
  • 资源分配:尽可能地利用可用资源达到最优解,例如,在预算限制下最大化收益。
  • 任务调度:在任务规划或调度问题中,基于某种优先级(如最早完成时间、最小持续时间等)来选择任务。 
  • 集合覆盖:在需要覆盖整个集合的问题中,每一步选择覆盖最多未覆盖元素的选项。
  • 动态规划简化:对于某些可以使用动态规划解决的问题,贪心算法提供了更高效的解决方案,尤其是当问题满足某种特定结构时。

5、案列

5.1、分配问题

题目描述: 有一群孩子和一堆饼干,每个孩子有一个饥饿度,每个饼干都有一个大小。每个孩子只能吃最多一个饼干,且只有饼干的大小大于孩子的饥饿度时,这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

输入输出样例

输入两个数组,分别代表孩子的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数量。
Input: [1,2], [1,2,3]
Output: 2

题解:

因为饥饿度最小的孩子最容易吃饱,所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子,所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后,我们采取同样的策略,考虑剩下孩子里饥饿度最小的孩子,直到没有满足条件的饼干存在。 简而言之,这里的贪心策略是,给剩余孩子里最小饥饿度的孩子分配最
 1 int findContentChildren(vector<int>& children, vector<int>& cookies) {
 2 sort(children.begin(), children.end());
 3 sort(cookies.begin(), cookies.end());
 4 int child = 0, cookie = 0;
 5 while (child < children.size() && cookie < cookies.size()) {
 6 if (children[child] <= cookies[cookie]) ++child;
 7 ++cookie;
 8 }
 9 return child;
10 }

题目描述:

一群孩子站成一排,每一个孩子有自己的评分。现在需要给这些孩子发糖果,规则是如果一个孩子的评分比自己身旁的一个孩子要高,那么这个孩子就必须得到比身旁孩子更多的糖果;所有孩子至少要有一个糖果。求解最少需要多少个糖果

输入输出样例 

输入是一个数组,表示孩子的评分。输出是最少糖果的数量。
Input: [1,0,2]
Output: 5

题解:

虽然这一道题也是运用贪心策略,但我们只需要简单的两次遍历即可:把所有孩子的糖果数初始化为 1;先从左往右遍历一遍,如果右边孩子的评分比左边的高,则右边孩子的糖果数更新为左边孩子的糖果数加 1;再从右往左遍历一遍,如果左边孩子的评分比右边的高,且左边孩子当前的糖果数不大于右边孩子的糖果数,则左边孩子的糖果数更新为右边孩子的糖果数加 1。通过这两次遍历,分配的糖果就可以满足题目要求了。 贪心策略即为,在每次遍历中,只考虑并更新相邻一侧的大小关系。
 1 int candy(vector<int>& ratings) {
 2 int size = ratings.size();
 3 if (size < 2) {
 4 return size;
 5 }
 6 vector<int> num(size, 1);
 7 for (int i = 1; i < size; ++i) {
 8 if (ratings[i] > ratings[i-1]) {
 9 num[i] = num[i-1] + 1;
10 }
11 }
12 for (int i = size - 1; i > 0; --i) {
13 if (ratings[i] < ratings[i-1]) {
14 num[i-1] = max(num[i-1], num[i] + 1);
15 }
16 }
17 return accumulate(num.begin(), num.end(), 0); // std::accumulate 可以很方便地求和
18 }

5.2、区间问题

题目描述 

给定多个区间,计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。 

输入输出样例

输入是一个数组,数组由多个长度固定为 2 的数组组成,表示区间的开始和结尾。输出一个整数,表示需要移除的区间数量。
Input: [[1,2], [2,4], [1,3]]
Output: 1
在这个样例中,我们可以移除区间 [1,3],使得剩余的区间 [[1,2], [2,4]] 互不重叠 

题解

在选择要保留区间时,区间的结尾十分重要:选择的区间结尾越小,余留给其它区间的空间就越大,就越能保留更多的区间。因此,我们采取的贪心策略为,优先保留结尾小且不相交的区间 具体实现方法为,先把区间按照结尾的大小进行增序排序,每次选择结尾最小且和前一个选择的区间不重叠的区间。我们这里使用 C++ 的 Lambda,结合 std::sort() 函数进行自定义排序。 在样例中,排序后的数组为 [[1,2], [1,3], [2,4]]。按照我们的贪心策略,首先初始化为区间[1,2];由于 [1,3] 与 [1,2] 相交,我们跳过该区间;由于 [2,4] 与 [1,2] 不相交,我们将其保留。因此最终保留的区间为 [[1,2], [2,4]]。
 1 int eraseOverlapIntervals(vector<vector<int>>& intervals) {
 2 if (intervals.empty()) {
 3 return 0;
 4 }
 5 int n = intervals.size();
 6 sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b) {
 7 return a[1] < b[1];
 8 });
 9 int total = 0, prev = intervals[0][1];
10 for (int i = 1; i < n; ++i) {
11 if (intervals[i][0] < prev) {
12 ++total;
13 } else {
14 prev = intervals[i][1];
15 }
16 }
17 return total;
18 }

5.3、买卖股票

题目描述

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。 

返回 你能获得的 最大 利润 。

输入输出样例

输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
题解

本题采用局部最优的方法,在遍历天数的过程中,时刻确认下一天和当天之间的利润,并且保证相加的时候,利润不可小于0,。其实本题可以抽象把价格数组,直接变成利润数组,转化为数组和这样的题目。因为只要保证当天存在利润,那么往后累加就一定是最大的利润

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         int result = 0;
 5         for(int i = 0;i<prices.size()-1;i++){
 6             result += max(prices[i+1]-prices[i],0);
 7         }
 8         return result;
 9     }
10 };

 

 

 

 

标签:int,孩子,问题,算法,区间,最优,贪心
From: https://www.cnblogs.com/Zhouce/p/18117074

相关文章

  • 调度算法
    调度算法评价指标CPU利用率由于早期的CPU造价极其昂贵,因此人们会希望让CPU尽可能多地工作CPU利用率:指CPU“忙碌”的时间占总时间的比例。Eg:某计算机只支持单道程序,某个作业刚开始需要在CPU上运行5秒,再用打印机打印输出5秒,之后再执行5秒,才能结束。在此过程中,CPU利用率、打......
  • 【算法】数论
    题目链接前言疑似是有点不会数学了,照着题解推式子都推了小半个下午,还看不出来减法公式,唉。题解考虑把这些\(f(a,b)\)异或起来再模一个数不会有很好的性质,所以要把每一个\(f(a,b)\)都算出来。由加法公式得\[f(a,b)=\sum\\tbinom{b}{i}\tbinom{n-i}{a}\]\[=\sum\tbin......
  • 排序算法——快速排序
    问题描述 现有一组数据:23,45,18,11,13,79,72,25,3,17,请使用快速排序算法将它们按照从小到大的顺序排列。算法思想(1)在无序数据中选一个基准数(通常为数据第一个);(2)将数据中小于基准数的数据移到基准数左边,大于基准数的移到右边;(3)对于基准数左、右两边的数据,不断重复以上两个......
  • 贪心算法|1005.K次取反后最大化的数组和
    力扣题目链接classSolution{staticboolcmp(inta,intb){returnabs(a)>abs(b);}public:intlargestSumAfterKNegations(vector<int>&A,intK){sort(A.begin(),A.end(),cmp);//第一步for(inti=0;i<A.size......
  • 操作系统综合题之“采用动态分区分配算法下的3种算法(首次适应算法、循环首次适应算法
    一、问题:当空闲链如下图,第一个空闲分区起始地址为20KB,大小为120KB;第二个空闲分区起始地址为200KB,大小为100KB;第三个空闲分区起始地址为400KB,大小为60KB。若某进程P1先申请大小为30KB的内存空间,随后进程P2再申请大小为20KB的内存空间,画出给P1分配完之后的空闲链和给P2分配完......
  • 强化学习算法性能表现
    各算法在不同环境中的表现:来自天寿基准测试https://tianshou.org/en/stable/01_tutorials/06_benchmark.html1.HalfCheetah-v3SAC>DDPG>TD3>PPO>TRPO>NPG>ACKTR>A2C>REINFORCE2.蚂蚁v3SAC>TD3>A2C>PPO>......
  • 因为算法不同,客户端与服务器无法通信。”的解决方法
    因为算法不同,客户端与服务器无法通信。”的解决方法sqlserver客户端远程sqlserver服务器 或是mstsc 最后根据微软文档的说明,改动注册表就成功了:传输层安全性(TLS)注册表设置|MicrosoftDocs在注册表编辑器,找到以下注册表项/文件夹:HKEY_LOCAL_MACHINE\SYSTEM\Curren......
  • Python算法学
    Python算法学习平台有很多,它们提供了丰富的资源和工具,帮助学习者从基础到高级的算法知识。以下是一些流行的Python算法学习平台:1.**LeetCode**:-网址:[https://leetcode.com/](https://leetcode.com/)-特点:LeetCode是一个非常受欢迎的在线编程平台,提供了大量的编程挑战,主......
  • CS202 WeensyOS 内存分配算法
    CS202:实验室4:WeensyOSCS202:实验室4:WeensyOS介绍在这个实验室中,您将在一个(但却是真实的!)操作系统,名为WeensyOS。这将向您介绍虚拟内存,并强化我们已经介绍过的一些概念学期WeensyOS内核在x86-64CPU上运行。因为操作系统内核运行在“裸”硬件上,所以调试内核代码可能很难:如果一个......
  • 常见的排序算法——插入排序
    本文记述了插入排序的基本思想和一份参考实现代码,并在说明了算法的性能后用实验进行了验证。◆思想将第一个元素之后的所有元素作为待排序范围,将前面的所有元素作为已排序范围。通过一一比较,逐个交换已排序范围内比第二个元素大的所有元素,使第二个元素被插入到了正确的位置。然......