贪心算法

一、题目（力扣455.分发饼干）

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/assign-cookies

二、贪心算法，也叫贪婪算法、偏心算法

核心思想：（引用《算法导论》）

贪心算法（greedy algorithm）就是这样的算法，它在每一步都做出当时看起来最佳的选择。也就是说，它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。

虽然不一定是全局最优解。

此题解题思想：胃口小的吃小的饼干，胃口大的吃大的饼干。

三、题解

先从胃口最小的孩子开始，拿最小的饼干看看能否满足他，如果不能，就找第二小的，以此类推。

public int findContentChildren(int[] g,int[] s){
    //先对胃口值和饼干大小进行排序
    Arrays.sort(g);
    Arrays.sort(s);

    //能满足的孩子的数量
    int count = 0;

    //能用count当胃口值g的索引，是因为是从胃口最小的孩子开始喂，如果某个孩子无法满足那么，胃口比这个孩子大的也不可能满足，到此循环就可结束
    for(int j = 0;count < g.length && j < s.length;j++){
        //如果第j个饼干满足第count个小孩，则下次循环尝试满足第count+1个小孩
        if(g[count] <= s[j]){
            count++;          
        }
        //如果无法满足则j++，即尝试下一个饼干
    }
    return count;
}