概述

贪心算法的思想非常简单：在对问题求解时，不从整体最优上加以考虑，而总是做出在当前看来是最好的选择。也就是说，所做出的是在某种意义上的局部最优解。

换句话说，与动态规划的全局性不同，贪心算法显得目光短浅，但是如果分析正确，并不会导致结果错误。

然而，贪心算法并不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态只与它前面出现的状态有关，而独立于后面的状态。
例如“数字金字塔”问题，就无法使用贪心算法，因为每层的路径选择都会影响后续的选择，当前的最优选择很可能会导致后续更大价值的路线被舍弃掉导致错误。

可以用贪心算法解决的问题有如下两个性质：

  • 贪心选择性质：所求的问题的整体最优解可以通过一系列局部最优的选择，也就是贪心选择得到。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题。
  • 最优子结构性质：即原问题的最优解包含的子问题的最优解，而且这些子问题可以独立求解，核心思想是“全局最优解包含局部最优解”。

特定问题的解决方式选择

算法核心：状态与状态的转移
对于一个特定的问题，用递推、贪心、搜索还是动态规划的哪一种方式来解决，是由其状态的转移方式决定的：

  • 每个阶段只有一个状态->递推；
  • 每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
  • 每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
  • 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

贪心和动态规划的区别

  1. 贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。
  2. 贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。
  3. 动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

本质上，贪心是一种特殊的动态规划，只不过由于其由于其具有贪心选择性质，因此保证了子问题只会被计算一次，不会被多次计算。

另一方面，关于 最优子结构性质：

  • 贪心的局部最优一定能达成全局最优
  • 动态规划的全局最优值中不一定全是局部最优，只是求解全局最优时要以局部最优作为基础

重要问题

分发饼干

题号：力扣455

很简单，将 g 和 s 从小到大排序即可，使用2个指针 i 和 j 逐个遍历；
如果当前 g[i]<=s[j]，那么i++;j++;，继续考虑下一个孩子和饼干；
否则 j++，尝试使用下一块饼干满足孩子，直到遍历完毕。

Go代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func findContentChildren(g []int, s []int) (ans int) {
    sort.Ints(g)
    sort.Ints(s)
    m, n := len(g), len(s)
    for i, j := 0, 0; i < m && j < n; i++ {
        for j < n && g[i] > s[j] {
            j++
        }
        if j < n {
            ans++
            j++
        }
    }
    return
}

无重叠区间

以右边界排序，然后进行枚举，维护当前right右边界，对不重叠的区间进行计数即可，最后用总区间数做差即可。
具体分析见力扣453官方题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func eraseOverlapIntervals(intervals [][]int) int {
    n := len(intervals)
    if n == 0 {
        return 0
    }
    sort.Slice(intervals,func(i,j int)bool{ return intervals[i][1] < intervals[j][1] })
    right := intervals[0][1]
    ans := 1
    for i:=1;i<n;i++{
        if intervals[i][0] >= right {
            ans++
            right = intervals[i][1]
        }
    }
    return n-ans
}

哈夫曼编码

略。。。

image.png

Prim算法和Kruskal算法

略。。。
都是要将权重排序，每次选取当前最小权重，让生成树生成或合并。

注：本文参考自课程ppt