算法-贪心算法

规律

贪心算法的规律是通过归纳找出局部的最优解，那么扩展下去找到的一定也是最优解

学习资料

https://www.ixigua.com/pseries/6803573365928886787_6803240858175930891/

1、找零问题
贪心算法找零问题，有面额为100, 50, 20, 10, 5, 1元的钞票，给定任意面额，要求使用最少张数的钞票，求钞票的张数

/**
   * 贪心算法找零问题，有面额为100, 50, 20, 10, 5, 1元的钞票，给定任意面额，要求使用最少张数的钞票，求钞票的张数
   * @param arr
   * @param money
   * @return
   */
  public static int greedy(int[] arr, int money){
    int temp= money;
    int count = 0;
    for (int i = 0; i < arr.length; i++) {
      if(temp>arr[i]){
        int x = temp / arr[i];
        System.out.println("需要取出面额为"+arr[i]+"的钞票"+x+"张");
        temp =temp % arr[i];
        count+=x;
      }
    }
    return count;
  }

2、饼干分发

/**
   * 455. 分发饼干
   * https://leetcode-cn.com/problems/assign-cookies/
   * 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i
   * ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；
   * 并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，
   * 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
   *
   * 注意：
   *
   * 你可以假设胃口值为正。
   * 一个小朋友最多只能拥有一块饼干。
   *
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/assign-cookies
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
   * @param g
   * @param s
   * @return
   */
public static  int findContentChildren(int[] g, int[] s) {
    /*
    思路
      1、先将孩子的胃口和饼干的尺寸进行一个排序，从小到大
      2、如果小尺寸的饼干能满足一个孩子，那就没有必要用更大尺寸的饼干，大尺寸的留给大胃口的孩子(贪心)
      3、假设孩子胃口数组g[2,5,9,9,10,15]  饼干尺寸s[1,3,6,8,20]
      4、建立两个指针，一个指向孩子，一个指向饼干
     */
    Arrays.sort(g);
    Arrays.sort(s);
    int child = 0;
    int cookie = 0;
    int count =0;
    while (cookie<s.length && child<g.length){
      if(s[cookie]<g[child]){
        //当前饼干不能满足，也就不能其他孩子，饼干指针后移
        cookie++;
      }else if(s[cookie]>g[child]){
        //当前饼干正好可以满足，分配饼干，并且孩子、饼干指针右移
        System.out.println(s[cookie]+"分给孩子"+g[child]);
        cookie++;
        child++;
        count++;
      }
    }
    return count;
  }