第6次课 贪心算法 A
向日葵朝着太阳转动，时刻追求自身成长的最大可能。
贪心策略在一轮轮的简单选择中，逐步导向最佳答案。
课堂学习
引入
贪心算法（英语：greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。
可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。
解释
适用范围
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。1
证明
贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明。
- 反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
- 归纳法：先算得出边界情况（例如
）的最优解 
，然后再证明：对于每个 
，
都可以由 
推导出结果。
要点
常见题型
在提高组难度以下的题目中，最常见的贪心有两种。
- 「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」。
- 「我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）
二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。
排序解法
用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。
后悔解法
思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。
区别
与动态规划的区别
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
小结
- 贪心算法通常用于解决最优化问题，其原理是在每个决策阶段都做出局部最优的决策，以期获得全局最优解。
- 贪心算法会迭代地做出一个又一个的贪心选择，每轮都将问题转化成一个规模更小的子问题，直到问题被解决。
- 贪心算法不仅实现简单，还具有很高的解题效率。相比于动态规划，贪心算法的时间复杂度通常更低。
- 在零钱兑换问题中，对于某些硬币组合，贪心算法可以保证找到最优解；对于另外一些硬币组合则不然，贪心算法可能找到很差的解。
- 适合用贪心算法求解的问题具有两大性质：贪心选择性质和最优子结构。贪心选择性质代表贪心策略的有效性。
- 对于某些复杂问题，贪心选择性质的证明并不简单。相对来说，证伪更加容易，例如零钱兑换问题。
- 求解贪心问题主要分为三步：问题分析、确定贪心策略、正确性证明。其中，确定贪心策略是核心步骤，正确性证明往往是难点。
- 分数背包问题在 0-1 背包的基础上，允许选择物品的一部分，因此可使用贪心算法求解。贪心策略的正确性可以使用反证法来证明。
- 最大容量问题可使用穷举法求解，时间复杂度为 O(n²)。通过设计贪心策略，每轮向内移动短板，可将时间复杂度优化至 O(n)。
- 在最大切分乘积问题中，我们先后推理出两个贪心策略：≥4 的整数都应该继续切分，最优切分因子为 3 。代码中包含幂运算，时间复杂度取决于幂运算实现方法，通常为 0(1)或O(logn)。
课堂训练
2909 贪心的小童
描述
兔子采集队工作回来，把采集回来的胡萝卜分成 4 堆,小童只能从每堆里拿走 1 根胡萝卜。
小童的目标是拿走总重量最重的 4 根胡萝卜。假如我们知道每根胡萝卜的重量，爱学编程的你来帮帮小童吧。
输入描述
4堆胡萝卜，共4行：每行第一个正整数n，是一堆胡萝卜的数量（≤1000）。后面n个正整数，是每堆胡萝卜中每个胡萝卜的重量（1≤单个胡萝卜重≤100）。
输出描述
请问拿走的4根胡萝卜总重量最大是多少？
样例输入 1
5 4 3 2 1 6 4 3 2 1 4 6 9 3 2 4 6 3 3 11 2 1
样例输出 1
30