力扣小白刷题之455分发饼干
题目描述
每个孩子最多只能给一块饼干，对于每个孩子 i，他的胃口值是 gi，即孩子能满足胃口的最小饼干尺寸；对于每块饼干 j，都有一个尺寸 sj。如果 sj >= gi，就可以将饼干 j 分给孩子 i，这个孩子就会得到满足。
目标是满足尽可能多数量的孩子，并输出这个最大值。
思路
贪心思想。
- 给一个孩子的饼干应该尽量小又能够满足该孩子，这样大饼干才能拿来满足需求大的孩子。
- 需求小的孩子越容易满足，所以先满足需求小的孩子。
在以上的解法中，我们只在每次分配时饼干时选择一种看起来是当前最优的分配方法，但无法保证这种局部最优的分配方法最后能得到全局最优解。我们假设能得到全局最优解，并使用反证法进行证明，即假设存在一种比我们使用的贪心策略更优的最优策略。如果不存在这种最优策略，表示贪心策略就是最优策略，得到的解也就是全局最优解。
证明：假设在某次选择中，贪心策略选择给当前满足度最小的孩子分配第 m 个饼干，第 m 个饼干为可以满足该孩子的最小饼干。假设存在一种最优策略，可以给该孩子分配第 n 个饼干，并且 m < n。我们可以发现，经过这一轮分配，贪心策略分配后剩下的饼干一定有一个比最优策略来得大。因此在后续的分配中，贪心策略一定能满足更多的孩子。也就是说不存在比贪心策略更优的策略，即贪心策略就是最优策略。