关于对贪心算法的理解

简介: 关于对贪心算法的理解

一.概念理解

1.何为贪心算法?

贪心算法(greedy algorithm [8] ,又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解 。

2.贪心算法的特征

1、有一个以最优方式来解决的问题。为了构造问题的解决方案,有一个候选的对象的集合:比如不同面值的硬币 。

2、随着算法的进行,将积累起其他两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象 。

3、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优 [3] 。

4、还有一个函数检查是否一个候选对象的集合是可行的,即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性 。

5、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解 。

6、最后,目标函数给出解的值


二.思路解析及结合具体题目进行贪心策略的选择sad

1.思路总述:

贪心算法是所有算法中最灵动的算法,对于贪心题目而言,我们解决问题的关键在于能够找到其正确的贪策略,但是说句实在话,对于不同的题目和应用场景,几乎每道题目都有属于自己的解题思路,我们能做的在很大程度上只能说是总结;与此同时,贪心算法同样也是最符合自然智慧的算法,贪心算法的起源来自于生活场景,因此,根据不同生活场景进行部署不同的贪心策略,同样有助于我们解决问题。


接下来,我们根据不同的题目进行不同贪心策略的部署:

1.会议问题

大家都知道,老板总是很忙,每天有很多会等着老板参加,但老板又没有时间参加所有的会议,所以需要秘书来合理安排。

某一天,老板对秘书说:“你安排一下,我希望今天尽可能多参加几场会议”。秘书看了一下如下希望老板参加的会议,她应该如何安排,才能使老板参加会议的场次最多? [[8,10],[9,11],[10,15],[11,14],[13,16],[14,17],[15,17],[17,18],[18,20],[16,19]] 列表里的每一个子列表都表示一场会议比如第一场会议[8,10],表示这场会议开始时间是8点,结束时间是10点。

image.png

我们试着分析一一下这个问题:如果想要合理安排会议以至于在一天中安排的会议场数最多,我们必须要找到一个标准来决定会议安排的时间先后问题,而这便是这个问题的贪心策略的着手点,那标准是会议开始的越早就先安排这场会议吗?(反例:如果一场会议从早上开到晚上结束呢?,这样只能安排一场会议了)这个策略显然不合理,与此相反,恰好是哪场会议结束的最早,我们先安排哪场会议(因为一天的时间是一定的,如果先安排早结束的会议,意味着我们有更多的时间去安排后面的会议,而这便是这个题目贪心策略的关键点)

image.png

基于这个思路,我们进行code:

public class ConferenceForGreedy {

   public static void main(String[] args) {

 

   }

   public int conferenceGreedy(Conference[]programs){

       if(programs==null||programs.length==0){

           return  0;

       }

       int result=0;

 

       int timeLine=0;

       //对数组进行排序

       Arrays.sort(programs,new sorts());

       //对数组进行遍历放入

       for (int i = 0; i < programs.length; i++) {

           if(programs[i].start>=timeLine){

               //符合条件就对会议的数量进行增加

               result++;

               //不断去更迭timeLine

               timeLine=programs[i].end;

           }

       }

       return result;

   }

//重写比较器,使结束时间早的会议排在数组的前面

  public static class sorts implements Comparator<Conference> {

      @Override

      public int compare(Conference o1, Conference o2) {

          return o1.end-o2.end;

      }

  }

}

2.股票抛售问题

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。返回 你能获得的 最大 利润 。

8eb336b37dee501069a7be67c652c3b7.png

image.png

我们通过上面的实例能够发现:我们能够预知未来(知道未来几天股票价格的跌落),如果在这样的情况下,那我们的贪心策略就很容易进行抉择了:第一天买入股票,如果预知到后面某一天股票价格跌落,就在前一天将股票进行抛售;如果后面的日子股票价格没有跌落,那我们就继续等待(赚更多的钱)

我们在这种思路下来code:

class Solution {

   public int maxProfit(int[] prices) {

       //思路:在当前情况下做出做优决定:如果股票在明天降价或者不变,我们就在今天卖出,如果价格上升,保留

       //检查数组的有效性

       if(prices.length==1){

           return 0;

       }

       int profits=0;

       //-1状态表示当前手中没有股票

       int tacket=-1;

       for(int i=0;i<prices.length-1;++i){

           if(tacket==-1){

               //买入

               tacket=prices[i];

           }

           if(prices[i+1]>prices[i]){

               //继续等待

               continue;

           }

           else{

               //进行抛售

               profits+=prices[i]-tacket;

               tacket=-1;

           }

       }

       //检查最后一天,不是0说明最后一天股票价格上涨

       if(tacket!=-1){

           profits+=prices[prices.length-1]-tacket;

       }

       return profits;

   }

}

3.路灯问题

给定一个字符串str,只由‘X’和‘.’两中国字符构成。

‘X’表示墙,不能放灯,也不需要点亮,‘.’表示居民点,可以放灯,需要点亮。

如果灯放在i位置,可以让i-1,i和i+1三个位置被点亮,返回如果点亮str中所需要点亮的位置,至少需要几盏灯

例如: X…X…X…X. 需要至少5盏灯

思路概述:这道题的关键点用一句话可以概括为用最少的灯点亮全部的居民点,我们按照不同的情况进行不同的策略部署:

image.png

在思路的指引下:我们直接进入code:

package greedy;

 

/**

* @author tongchen

* @create 2023-03-09 9:31

*/

public class LightForGreedy {

   public static void main(String[] args) {

 

   }

   public int PlacesForGreedy(char[]chars){

       int index=0;//遍历变量

       int lights=0;

       while(index<chars.length){

           //当前位置为x则直接跳过

           if(chars[index]=='X'){

               index++;

           }

           else {

               //因为要考虑当前位置+1的内容,所以我们必须判断当前位置是不是在数组的最后

               //在index index+1 和index+2 的区间内,必定放一个灯

               lights++;

               if(chars[index+1]==chars.length){

                   //如果是最后一个元素,直接返回

                   break;

               }

               if(chars[index+1]=='X') {

                   //下一个位置为X,跳跃到下下个位置

                   index+=2;

               }

               else {

                   //这种情况则为下一个位置为.  不论index+2的位置是.还是X,直接跳跃到index+3的位置

                   index+=3;

               }

           }

       }

       //返回放置路灯的数量

       return  lights;

   }

}

通过这三个题目,我们能够总结一点:不同的贪心题目具有不同的应用场景,贪心策略也随之有所变化,

除了找到正确的贪心策略之外,我们仍然可以采用“试”的方法求得最优解:

我们拿会议问题和路灯问题来给出代码实例:

  1. 会议问题

package greedy;

 

/**

* @author tongchen

* @create 2023-03-09 8:09

*/

public class ConferenceForViolence {

   public static void main(String[] args) {

 

   }

   //创建不断递归的主方法

   public  int process(Conference[]programs,int done,int timeLine){

       //出口条件:判断所有的事务是否都已完成

       if( 0==programs.length){

           return 0;

       }

       //继承上面做的事务数量

       int max=done;

       //循环:处理当前事务,并判断下面的事务(以当前事务为第一个事务,不断进行暴力枚举)

       for(int i=0;i<programs.length;++i){

           if(programs[i].start>=timeLine){

               //没有需要处理的,直接跨入下一个

               Conference[] conferences = copyButExpect(programs, i);

           max=Math.max(max,  process(conferences, done+1, programs[i].end));

           }

       }

       return max;

   }

   //创建获取新数组的方法

   public Conference[] copyButExpect(Conference[]programs,int i){

       //创建新的数组

       Conference[] arr=new Conference[programs.length-1];

       int count=0;

       //定义计数器

       for(int k=0;k< programs.length;++i){

           if(k!=i){

               arr[count++]=programs[k];

           }

       }

       return arr;

   }

 

}

  1. 路灯问题

package greedy;

 

import java.util.HashSet;

 

/**

* @author tongchen

* @create 2023-03-09 9:01

* 思路:循环处理灯:判断当前位置为X的时候不做选择,当前位置是.的时候选择放入和不放入

*/

public class LightsForViolence {

   public static void main(String[] args) {

 

   }

   public int process(char[]places, int index, HashSet<Integer>lights){

       //当index走到最后的时候,从头到尾依次判断这次的放入灯的策略是否正确

       if(index==places.length){

           //遍历检查有效性

           for (int i = 0; i < places.length; i++) {

               if(places[i]!='X'){

                   if(lights.contains(i-1)&&lights.contains(i)&&lights.contains(i+1)){

                       //这种情况不合理

                       return  Integer.MAX_VALUE;

                   }

               }

           }

           return lights.size();

       }else {

           //没有走到最后

           int no=process(places, index+1, lights);

           int yes=Integer.MAX_VALUE;

 

           if(places[index]=='.'){

               lights.add(index);

                yes=process(places, index+1, lights);

           }

 

 

           return Math.min(yes,no);

       }

   }

 

}

这三个题目只是贪心问题中的冰山一角:

另外我还做了其他的一些关于贪心问题的题目,并总结了贪心策略,希望能给大家带来一些启发。


三.总结概括

我们通过上面的例子更能清楚的感受到不同题目所采用的的贪心算法的多样性和灵活性,在一定程度上很难在其中找到固定的解法,但是我们仍能从其中找到一些普适的规律:很多贪心题目都能在进行特定的排序或者将其放入按照某些属性进行排序的大跟堆和小根堆中,往往有可能能够找到正确的贪心策略。



相关文章
|
移动开发 算法 调度
【贪心算法】一文让你学会“贪心”(贪心算法详解及经典案例)
贪心算法是一种非常常见的算法,它的简单和高效性使其在实际应用中被广泛使用。 贪心算法的核心思想是在每一步都采取当前状态下最优的选择,而不考虑未来可能产生的影响。虽然贪心算法不能保证总是得到最优解,但在很多情况下,它可以获得很好的结果。 本篇文章将介绍贪心算法的基本概念和一些经典应用,以及如何通过贪心算法来解决一些实际问题。希望通过本文的阅读,读者可以对贪心算法有更加深刻的理解,并能够在实际问题中应用贪心算法来得到更好的解决方案。 让我们暴打贪心算法吧!
6173 0
|
12月前
|
人工智能 算法 安全
详解贪心算法
详解贪心算法
|
7月前
|
数据可视化 数据挖掘 Java
报表工具怎么选?8款主流报表工具大测评!
报表工具怎么选?8款主流报表工具大测评!
|
11月前
|
安全 前端开发 云计算
Waline:一款开源、安全、简介的评论系统
阿里云计算巢提供了一键部署waline的功能,无需下载代码或安装复杂依赖,通过简单步骤即可搭建waline —— 一款带后端的极简风评论系统。
Waline:一款开源、安全、简介的评论系统
|
10月前
|
机器学习/深度学习 人工智能 编译器
【AI系统】死代码消除
死代码消除是一种编译器优化技术,旨在移除程序中不会被执行的代码,提升程序效率和资源利用。通过分析控制流图,识别并删除不可达操作和无用操作,减少不必要的计算。在传统编译器中,主要通过深度优先搜索和条件分支优化实现;而在AI编译器中,则通过对计算图的分析,删除无用或不可达的计算节点,优化模型性能。
324 3
|
11月前
|
存储 数据采集 人工智能
TDengine 签约蘑菇物联,改造通用设备工业互联网平台
在当前工业互联网迅猛发展的背景下,企业面临着日益增长的数据处理需求和智能化转型的挑战。通用工业设备的高能耗问题愈发突出,尤其是由这些设备组成的公辅能源车间,亟需更高效的解决方案来提升设备运行效率,降低能源消耗。为此,蘑菇物联选择携手 TDengine,共同推进数智化转型。
206 3
|
12月前
|
机器学习/深度学习 人工智能 算法
【大语言模型-论文速读】GPT的不确定性判断
【大语言模型-论文速读】GPT的不确定性判断
147 0
|
12月前
|
机器学习/深度学习 人工智能 算法
【AI系统】AI的历史、现状与理论基础
人工智能(AI)作为一门跨学科的研究领域,其目标是模拟、延伸和扩展人的智能。本文旨在概述AI的历史发展、当前趋势以及理论基础,为读者提供一个系统的视角。
381 0
|
JSON 前端开发 数据格式
Controller方法层POST请求方式代码形参接收不到问题
Controller方法层POST请求方式代码形参接收不到问题
321 0
|
人工智能 API 数据中心
NVIDIA破局第二曲线创新问题之Megatron Core的定义如何解决
NVIDIA破局第二曲线创新问题之Megatron Core的定义如何解决
196 0