关于对贪心算法的理解

朱雀 2024-03-25 11:50 34阅读 0赞

一.概念理解

1**.何为贪心算法？**

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

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点。

![8e31b3330ff814ad9dce092dacc2db9f.png][]

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

![3dea38196a296b98db66e6091db3f33c.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][]

![cc53b14b1983e7d9e4dc8139037a10ac.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盏灯  
> 思路概述：这道题的关键点用一句话可以概括为用最少的灯点亮全部的居民点，我们按照不同的情况进行不同的策略部署：  
>

![e03c0325c0ec1fbb3237c387be965f4c.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);
            }
        }
    
    }

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

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

链接如下：

三.总结概括

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

[Link 1]: https://baike.baidu.com/item/%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3/6693186?fromModule=lemma_inlink
[Link 2]: https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025?fromModule=lemma_inlink
[8e31b3330ff814ad9dce092dacc2db9f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/77e6ee520c234b99b11a8fa610da2dfa.png
[3dea38196a296b98db66e6091db3f33c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ba1bdbd9c09a463c9996ef974adf405e.png
[8eb336b37dee501069a7be67c652c3b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/357481a096154a349acfea142ee3562b.png
[cc53b14b1983e7d9e4dc8139037a10ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a0ca56afb9f741a5ba9040830de58181.png
[e03c0325c0ec1fbb3237c387be965f4c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5d8d8e2d74e74930974419aeebd082c5.png