【贪心算法】之分饼干

文章目录

• • 什么是贪心
  • • 分饼干问题

什么是贪心

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

这么说有点抽象，来举一个例子：

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

分饼干问题

大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

public class leetcode_455 {public static void main(String[] args) {int[] g = {1, 2};int[] s = {1, 2, 3};System.out.println(meet(g, s));}public static int meet(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int j = s.length - 1;int index = 0;for (int i = g.length - 1; i >= 0; i--) {if (j >= 0 && s[j] >= g[i]) {j--;index++;}}return index;}}