贪心算法
概述
贪心算法，又名贪婪算法。以下棋为例，每步的决策都需要考虑对后续棋局的影响。而在网球（或排球）比赛中，选手的行为仅取决于当前的状况，选择当下最为正确的动作，而不关心后续的影响 这说明在某些情况下选择当下最佳行为的决策，可以得到一个最优解（贪婪），但并非所有情况都如此，贪婪策略适用于上述第二类问题。即将问题分为多个阶段，在每一个阶段，选取当前状态下的最优决策，而不考虑对后续决策的影响。这意味着算法在执行过程中会选取某些局部最优解。贪婪假设通过局部最优解可以获得全局最优解。
要素
最优贪婪算法需要满足两个基本性质 ：
贪婪选择性质。
最优子结构
贪婪选择性质： 全局最优解可以通过寻找局部最优解获得（贪婪），局部最优解的
择可能依赖于之前的决策，而不是后续的决策 通过迭代方式算法进行 个个贪婪选择，
将原问题简化为规模更小的问题
最优子结构： 如果原问题的最优解包含子问题的最优解，则认为该问题具有最优子
结构。这意味着可以对子问题求解并构建规模更大问题的解。
基本思想
通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。所做的每一步选择都必须满足:
可行的:必须满足问题的约束。
局部最优:当前所有可能的选择中最佳的局部选择。
不可取消:选择一旦做出，在后面的步骤中就无法改变了。
局限性
不能保证总能得到最优解（一系列的局部最优选择不能保证最后得到整体最优解）
不能用来求最大值或最小值问题
只能求满足某些约束条件的可行解的范围。
优缺点
优点是直观，易于理解，并易于编码实现。当前的决策不会对已经计算出的结果有任何影响，因此不需要再对已有的局部解进行检查。
缺点是，对于许多问题，无法用贪婪算法求解。即在许多情况下，无法保证局部最优解能够产生全局最优解
应用
排序问题：选择排序、拓扑排序
优先队列：堆排序
赫夫曼编码压缩算法
Prim和 Krukal 算法
加权图的最短路径问题（ stra 算法）
硬币找零问题
分数背包问题
并查集的按大小或高度合并问题（或排名）
任务调度算法
贪婪算法可用于求解复杂问题的近似算法。
实际生活例子
找钱问题:
设有4种硬币，面值分别为25分，10分，5分和1分，要找出63分钱，问如何找钱可使得找出的硬币个数最少？
63=25+25+10+1+1+1
另一个找钱问题:
设有3种硬币，面值分别为25分，10分和1分，要找出30分钱，问如何找钱可使得找出的硬币个数最少?
分析：如使用贪心算法：30分钱，在面值25分，10分和1分找出最优为25分，然后进行下一步，只能选面值为1分的硬币，故以贪心算法最终算得的硬币数为6个。并不如3个面值为10分的个数少。故不可使用贪心算法。
30=25+1+1+1+1+1 六个硬币
30=10+10+10 三个硬币
代码例子
LeetCode1710. 卡车上的最大单元数
请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
numberOfBoxesi 是类型 i 的箱子的数量。
numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。
整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。
返回卡车可以装载 单元 的 最大 总数。
示例 1：
输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出：8
解释：箱子的情况如下：
- 1 个第一类的箱子，里面含 3 个单元。
- 2 个第二类的箱子，每个里面含 2 个单元。
- 3 个第三类的箱子，每个里面含 1 个单元。
可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8
示例 2：
输入：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
输出：91
提示：
1 <= boxTypes.length <= 1000
1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
1 <= truckSize <= 106
思路：
题目要求的是：
boxTypes 是二维数组 ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
numberOfBoxesi 是类型 i 的箱子的数量。
numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。
只要箱子数量不超过 truckSize，尽可能多的 以装载 单元 的 ，
换个思路就是说，numberOfBoxesi 表示有多少个箱子，numberOfUnitsPerBoxi，箱子的大小是多少个，但是题目给的是箱子的上限，所以，我们的是不是可以理解，只要箱子越大（也就是某一类的箱子可以装载的单元越多），就可以装更多的单元，所以我们根据 numberOfUnitsPerBoxi （每个箱子的大小）进行排序
初始代码模板
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
}
}
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
Arrays.sort(boxTypes, (o1, o2) -> o2[1] - o1[1]);
int ans = 0;
for (int i = 0; i < boxTypes.length; i++) {
if (truckSize > boxTypes[i][0]) {
ans += boxTypes[i][0] * boxTypes[i][1];
truckSize -= boxTypes[i][0];
} else {
ans += truckSize * boxTypes[i][1];
break;
}
}
return ans;
}
}
LeetCode455. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
提示：
1 <= g.length <= 3 * 10(4)
0 <= s.length <= 3 * 10(4)
1 <= g[i], s[j] <= 2(31) - 1
思路
大尺寸饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。
局部最优：大尺寸饼干先喂饱胃口大的，充分利用饼干尺寸。
全局最优：喂饱尽可能多的小孩。 尝试贪心算法添加链接描述，先把饼干数组和小孩数组排序。然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int start = s.length-1;
for(int index = g.length-1; index >= 0; index--){
if(start >= 0 && g[index] <= s[start]){
start--;
count++;
}
}
return count;
}
}
