算法思想
贪心算法
分而治之（递归思想）
动态规划
暴力穷举

贪心算法有哪些算法？

引入

思考：
假设有四种硬币，面值分别为50元、10元、5元和1元。
现在要找给某顾客113元，你会怎么找？

我们不假思索的就会选择2个50元，1个10元和3个1元的组合。

而我们的下意识的使用了找硬币算法：
1. 首先选取一个不大于113元的最大面值，即50元，剩余63待找。
2. 再选取一个不大于63元的最大面值，即又一个50元，剩余13待找
3. 再选取一个不大于13元的最大面值，即10元，剩余3待找
4. 剩下就是3个1元的硬币

贪心算法图解？我们每次都在范围内选最大价值的硬币，这样的方法实际上就是贪心算法。

基础知识

• 什么是贪心？
  局部最优，不考虑整体最优
  每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致全局结果是最好或最优的算法。

• 特点
  优点：做决策所需的计算复杂度较低
  缺点：贪婪、鼠目寸光，最终得到的解不一定是最优解

如果硬币的面值改为1元、5元和11元3种，需要找给顾客15元呢？

贪心算法模型。这个时候我们如果用贪心策略，得到的结果应该是1个11元+4个1元
但其实最优解是：3个5元！
所以说贪心最终得到的解不一定是最优解，但可能是近似最优解

• 什么时候用贪心？
  1. 最优子结构
     题目为解决最优化，而求解此类问题需要通过一系列的求解子问题完成。
  2. 贪心选择性质
     一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作 出的选择，但不依赖于后面要作出的选择

典型应用：找硬币、区间调度（活动安排）问题、普通背包问题、多机调度问题、Dijkstra等等

没有固定的套路和题型，贪心只是提供一种解题思路，手动模拟一下，如果找不出反例，就可以试试贪心~

贪心三步走

第一步：明确什么是最优解
第二步：明确子问题的最优解（重点：找策略）
第三步：分别求出子问题的最优解，再堆叠出全局最优解

举例

题目：
有一个背包，背包容量是M=150。
现有7个物品，要求尽可能让装入背包中的物品总价值最大，但不能超过总容量，物品可分割。

三步走：
第一步：明确什么是最优解
据题可知，选择某些物品的情况下，不超过重量范围（总m <=150）且物品总价值最大

第二步：明确子问题的最优解
子问题：每次选择一个物品放入背包
子问题最优解策略：

1. 价值最高
2. 重量最小
3. “价值密度”最高

第三步：分别求出子问题的最优解，再堆叠出全局最优解

1. 当选择 “价值最高” 策略时，按照规则（价值）进行计算，
   顺序为：D B F E， 重量 130， 价值165
2. 当选择 “重量最小” 策略时，按照规则（重量）进行计算，
   顺序为：F G B A E ， 重量 140， 价值155
3. 当选择 “价值密度” 策略时，按照规则（重量）进行计算，
   顺序为：F B G D A ， 重量 150， 价值175

综上，“利用价值密度选取物品”是这道普通背包题的局部最优解策略。

如果我们沿用以上背包问题贪心的最优策略，放在 0-1背包问题¹ 中呢？

题目：
现有背包容量M=50，有如下三个物品，物品不可分割，怎样让装入背包中的物品总价值最大？

物品1：6元/kg，物品2：5元/kg，物品3：4元/kg
依照价值密度规则，物品1最高。但首选物品1却不能获得最优解：

面对0-1背包问题，即使再优秀的贪心策略，也没有办法保证得到最优解。

因为无法保证最终能将背包装满，部分背包空间的闲置使每千克背包空间所具有的价值降低了
追求高价值(性价比)的物品是我们想要的，但同时不浪费过多背包的容积也是需要的

例题分享

1. 435-无重叠区间（活动调度问题）（Medium）
   https://leetcode-cn.com/problems/non-overlapping-intervals/
2. 738-单调递增的数字（Medium）
   https://leetcode-cn.com/problems/monotone-increasing-digits/
3. 435-无重叠区间（Medium）
   https://leetcode-cn.com/problems/non-overlapping-intervals/

题解：leetcode题解——贪心