贪心算法-蓝桥杯

一、贪心算法的优缺点

• 优点：

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号)

---

• 代码

五、真题实例(775号)

---

• 代码

六、贪心算法其它真题