贪心算法-分发饼干

前言

贪心算法（Greedy Algorithm）是一种常用的优化算法，它在每一步选择中都采取当前状态下最优的选择，以期望达到全局最优解。

分发饼干

leetcode-455 简单

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

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

局部最优：既能满足孩子，还消耗最少。

1. 对饼干数组和胃口数组升序排序。
2. 遍历饼干数组，找到能满足第一个孩子的饼干。
3. 然后继续遍历饼干数组，找到满足第二、三、……、n个孩子的饼干。

function findContentChildren(g,s) {
    // 升序排序
    const sort = (a,b) => a - b;
    g.sort(sort);
    s.sort(sort);
    let i = 0;
    s.forEach(n => {
        if (n >= g[i]) {
            i++;
        }
    })
    return i
}

go代码演示：

package main

import (
	"fmt"
	"sort"
)

// 分饼干
func findContentChildren(g, s []int) int {
	sort.Ints(g)
	sort.Ints(s)
	i := 0
	for n := range s {
		if n >= g[i] {
			i++
		}
	}
	return i
}

func main() {
	g := []int{1, 2}
	s := []int{1, 1, 3}

	n := findContentChildren(g, s)
	fmt.Println(n)
}