贪心算法-蓝桥杯

悠悠 2023-09-24 18:21 11阅读 0赞

# **一、贪心算法的优缺点** #

*  **优点：**

**1.容易理解:生活常见。**

**2.操作简单:在每一步都选局部最优。**

**3.效率高: 复杂度常常是O(1)的。**

*  **缺点：**

**1.局部最优不一定是全局最优。**

# **二、例子: 最少硬币问题** #

*  **硬币面值1、2、5。支付13元，要求硬币数量最少。**

*  **贪心法:**

**(1) 5元硬币，2个**

**(2) 2元硬币，1个**

**(3) 1元硬币，1个**

--------------------

*  **硬币面值1、2、4、5、6。支付9元，要求硬币数量最少。**

*  **贪心法:**

**(1) 6元硬币，1个**

**(2) 2元硬币，1个**

**(3) 1元硬币，1个**

*  **错误! 答案是:5元硬币+4元硬币。**

--------------------

*  **硬币问题的正解是动态规划。**

# **三、贪心和动态规划** #

*  **贪心法求解的问题满足以下特征:**

**(1) 最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。从局部最优能扩展到全局最优。**

**(2) 贪心选择性质。问题的整体最优解可以通过一系列局部最优的选择来得到。**

*  **动态规划:**

**(1) 重叠子问题:子问题是原大问题的小版本；计算大问题的时候，需要多次重复计算小问题。**

**(2) 最优子结构:大问题的最优解包含小问题的最优解；可以通过小问题的最优解推导出大问题的最优解。**

# **四、真题实例(1513号)** #

![cbb74e43c81547c99361861e5bf97fe2.png][]

![4c8c9b6905264af2b68ff42d54daa178.png][]

--------------------

*  **代码**

![ec1238263936444e91e7769734074d13.png][]

# **五、真题实例(775号)** #

![73750388ee354a1480bfa3528afa0db9.png][]

![ab7ed1f09c0a40ccbe08cf977e65eff4.png][]

--------------------

*  **代码**

![3db1ee21317b492fa75e69097cd0e33f.png][]

# **六、贪心算法其它真题** #

![64b31d7265ff4ca79aad16a643fdcbfd.png][]

[cbb74e43c81547c99361861e5bf97fe2.png]: https://img-blog.csdnimg.cn/img_convert/cbb74e43c81547c99361861e5bf97fe2.png
[4c8c9b6905264af2b68ff42d54daa178.png]: https://img-blog.csdnimg.cn/img_convert/4c8c9b6905264af2b68ff42d54daa178.png
[ec1238263936444e91e7769734074d13.png]: https://img-blog.csdnimg.cn/img_convert/ec1238263936444e91e7769734074d13.png
[73750388ee354a1480bfa3528afa0db9.png]: https://img-blog.csdnimg.cn/img_convert/73750388ee354a1480bfa3528afa0db9.png
[ab7ed1f09c0a40ccbe08cf977e65eff4.png]: https://img-blog.csdnimg.cn/img_convert/ab7ed1f09c0a40ccbe08cf977e65eff4.png
[3db1ee21317b492fa75e69097cd0e33f.png]: https://img-blog.csdnimg.cn/img_convert/3db1ee21317b492fa75e69097cd0e33f.png
[64b31d7265ff4ca79aad16a643fdcbfd.png]: https://img-blog.csdnimg.cn/img_convert/64b31d7265ff4ca79aad16a643fdcbfd.png