常用算法之贪心

迈不过友情╰ 2022-08-13 12:54 175阅读 0赞

**  一、背景**

在软考的准备中，遇到了算法，听过来人收，算法研究好了就很简单，研究不好就觉得很难，于是想着对算法做个总结，因为算法不仅仅在大题中占有15分，而且在选择题中同样也会出现，尤其是考复杂度和各种算法的适用情况，

贪心（目光短浅）：就像找男女朋友一样，**不求最好，只求合适（可行解）  **

**          二、如何知道在某种情况下用贪心是合适的呢？**

**       **  贪心策略适用的前提是：局部最优策略能**导致产生全局最优解。**

实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

** 三、贪心算法实现的基本步骤：**

##             1、候选集合(C) ##

通过一个候选集合C作为问题的可能解。（最终解均取自于候选集合C）

例如，在找零钱问题中，各种面值的货币构成候选集合。

**2、解集合(S)**

每完成一次贪心选择，将一个解放入S，最终获得一个完整解S

##          3、解决函数(solution) ##

检查解集合S是否构成问题的完整解。

例如，在找零钱问题中，解决函数是已付出的货币金额恰好等于应付款。

##         　4、选择函数(select) ##

即贪心策略，这是贪心法的关键，选择出最有希望构成问题的解的对象。（这个选择函数通常和目标函数有关）

例如，在找零钱问题中，贪心策略就是在候选集合中选择面值最大的货币。

## 　　    5、可行函数(feasible) ##

检查解集合中加入一个候选对象是否可行。（加入下一个对象后是不是满足约束条件）

例如，在找零钱问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。

**四、贪心算法的实现框架**

从问题的某一初始解出发；

while （能朝给定总目标前进一步）

\{

利用可行的决策，求出可行解的一个解元素；

\}

由所有解元素组合成问题的一个可行解；

**用C解释如下：**

<span style="font-size:14px;">Greedy(C)  //C是问题的输入集合即候选集合  
      
    {  
      
        S={ }; //初始解集合为空集  
      
        while (not solution(S))  //集合S没有构成问题的一个解  
      
        {  
      
           x=select(C);    //在候选集合C中做贪心选择  
      
           if feasible(S, x)  //判断集合S中加入x后的解是否可行  
      
              S=S+{x};  
      
              C=C-{x};  
      
        }  
      
        return S;  
      
    }  
    </span>

发表评论取消回复

表情：

评论列表（有 0 条评论，175人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构与算法之贪心算法】贪心算法的基本思想

【数据结构与算法之贪心算法】贪心算法的基本思想文章目录【数据结构与算法之贪心算法】贪心算法的基本思想贪心算法的优点是效率较高，实现较为简单

深碍√TFBOYSˉ_/ 2024年03月25日 19:16/ 0 赞/ 62 阅读

相关贪心算法之跳跃游戏

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

客官°小女子只卖身不卖艺/ 2023年01月02日 11:27/ 0 赞/ 157 阅读

相关贪心算法之纸币问题

纸币问题相信大家很熟悉了这里提出一个问题：设：有1，5，11这三种纸币，每种纸币足够多，问：至少需要多少张纸币才能凑够136元呢动起笔，写写画画，最后得出的结

深藏阁楼爱情的钟/ 2022年11月25日 04:14/ 0 赞/ 228 阅读

相关算法基础之贪心

算法基础之贪心（C++示例）贪心算法（greedy algorithm），是用计算机来模拟一个“贪心”的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最

青旅半醒/ 2022年09月05日 13:55/ 0 赞/ 209 阅读

相关五大常用算法之贪心算法

看了 [五大常用算法之一][Link 1] 这篇博文，感觉理解了很多，可是纯粹都是理论，缺少一些示例，所以准备综合一篇博文，以帮助自己记忆，原文： [http://ww

Love The Way You Lie/ 2022年08月24日 06:06/ 0 赞/ 165 阅读

相关常用算法之贪心

一、背景在软考的准备中，遇到了算法，听过来人收，算法研究好了就很简单，研究不好就觉得很难，于是想着对算法做个总结，因为算法不仅仅

迈不过友情╰/ 2022年08月13日 12:54/ 0 赞/ 176 阅读

相关五大常用算法之三：贪心算法

转自 [贪心算法][Link 1] 贪心算法一、基本概念：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是

╰半夏微凉°/ 2022年07月28日 09:23/ 0 赞/ 169 阅读

相关算法进阶之贪心算法

看着大家都在对自己学习过的算法进行总结，我也记录一下吧！从贪心算法开始！【前言】

迷南。/ 2022年06月08日 11:15/ 0 赞/ 213 阅读

相关五大常用算法之三：贪心算法

一、基本概念：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

分手后的思念是犯贱/ 2022年04月11日 14:41/ 0 赞/ 251 阅读

相关 [leetcode]贪心算法之WiggleSubsequence

贪心算法之WiggleSubsequence 题目思考代码题目 [leetcode入口][leetcode] 思考而是维护两个变

客官°小女子只卖身不卖艺/ 2021年09月28日 14:52/ 0 赞/ 274 阅读