贪心算法

概述

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法

贪心算法解决问题的正确性虽然很多时候都看起来是显而易见的，但是要严谨地证明算法能够得到最优解，并不是件容易的事。所以，很多时候，我们只需要多举几个例子，看一下贪心算法的解决方案是否真的能得到最优解就可以了。

适用情况

贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

贪心算法的2个条件：

最优子结构性质
如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。
贪心选择性质
对于某个问题，如果我们可以通过做出局部最优（贪心）选择来构造全局最优解，那么我们就称该问题具有贪心选择性质。

基本步骤

第一步，当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。

第二步，我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。

第三步，我们举几个例子看下贪心算法产生的结果是否是最优的。
大部分情况下，举几个例子验证一下就可以了。严格地证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。而且，从实践的角度来说，大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明。

实战分析

1 分糖果

我们有 m 个糖果和 n 个孩子。我们现在要把糖果分给这些孩子吃，但是糖果少，孩子多（m<n），所以糖果只能分配给一部分孩子。 每个糖果的大小不等，这 m 个糖果的大小分别是 s1，s2，s3，……，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。假设这 n 个孩子对糖果大小的需求分别是 g1，g2，g3，……，gn。
我的问题是，如何分配糖果，能尽可能满足最多数量的孩子？

问题抽象：从 n 个孩子中，抽取一部分孩子分配糖果，让满足的孩子的个数（期望值）是最大的。这个问题的限制值就是糖果个数 m。
使用贪心算法来解决：

1. 对于一个孩子来说，如果小的糖果可以满足，我们就没必要用更大的糖果。
2. 另一方面，对糖果大小需求小的孩子更容易被满足，所以，我们可以从需求小的孩子开始分配糖果。
3. 因为满足一个需求大的孩子跟满足一个需求小的孩子，对我们期望值的贡献是一样的。
4. 我们每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。

2 区间覆盖问题

假设我们有 n 个区间，区间的起始端点和结束端点分别是 [l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。我们从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？
类似场景：任务调度、教师排课

image.png
image.png
问题抽象：

1. 从n个区间中，满足两两不相交
2. 区间的个数（期望值）是最大的。

使用贪心算法来解决：

1. 将所有区间从左至右排列
2. 子问题：让达到一个期望(得到一个不相交区间)时，rx所在位置尽可能靠左（因为后续区间越容易满足不相交）。则rx 即为当前期望下rx的最优解。

3 霍夫曼编码

假设我有一个包含 1000 个字符的文件，每个字符占 1 个 byte（1byte=8bits），�存储这 1000 个字符就一共需要 8000bits，那有没有更加节省空间的存储方式呢？

问题抽象：

1. 总的字符加权和最小（字符*频率加和）

使用贪心算法来解决：

1. 频率高的占用字符尽可能少
   image.png
   霍夫曼树动态创建过程：
   霍夫曼树动态创建过程演示

定义霍夫曼树结构

package huffman

import (
    "container/heap"
    "fmt"
)

type HuffmanTree interface {
    Freq() int //频率
}

type HuffmanLeaf struct {
    freq  int
    value rune
}

type HuffmanNode struct {
    freq        int
    left, right HuffmanTree
}

func (self HuffmanLeaf) Freq() int {
    return self.freq
}

func (self HuffmanNode) Freq() int {
    return self.freq
}

实现优先队列，使用container/heap 包

type treeHeap []HuffmanTree

func (th treeHeap) Len() int { return len(th) }
func (th treeHeap) Less(i, j int) bool {
    return th[i].Freq() < th[j].Freq()
}
func (th *treeHeap) Push(ele interface{}) {
    *th = append(*th, ele.(HuffmanTree))
}
func (th *treeHeap) Pop() (popped interface{}) {
    popped = (*th)[len(*th)-1]
    *th = (*th)[:len(*th)-1]
    return
}
func (th treeHeap) Swap(i, j int) { th[i], th[j] = th[j], th[i] }

构建霍夫曼树

func buildTree(symFreqs map[rune]int) HuffmanTree {
    var trees treeHeap
    for c, f := range symFreqs {
        trees = append(trees, HuffmanLeaf{f, c})
    }
    heap.Init(&trees)
    for trees.Len() > 1 {
        a := heap.Pop(&trees).(HuffmanTree)
        b := heap.Pop(&trees).(HuffmanTree)

        heap.Push(&trees, HuffmanNode{a.Freq() + b.Freq(), a, b})
    }
    return heap.Pop(&trees).(HuffmanTree)
}

输出霍夫曼编码表

func printCodes(tree HuffmanTree, prefix []byte) {
    switch i := tree.(type) {
    case HuffmanLeaf:
        fmt.Printf("%c\t%d\t%s\n", i.value, i.freq, string(prefix))
    case HuffmanNode:
        prefix = append(prefix, '0')
        printCodes(i.left, prefix)
        prefix = prefix[:len(prefix)-1]

        prefix = append(prefix, '1')
        printCodes(i.right, prefix)
        prefix = prefix[:len(prefix)-1]
    }
}

运行测试

func TestHuff(t *testing.T) {
    test := "aaaaabbbbcccdd"

    symFreqs := make(map[rune]int)
    for _, c := range test {
        symFreqs[c]++
    }

    // example tree
    exampleTree := buildTree(symFreqs)

    // print out results
    fmt.Println("SYMBOL\tWEIGHT\tHUFFMAN CODE")
    printCodes(exampleTree, []byte{})
}

输出结果：

=== RUN   TestHuff
SYMBOL  WEIGHT  HUFFMAN CODE
a   5   0
b   4   10
d   2   110
c   3   111
--- PASS: TestHuff (0.00s)
PASS

4 N位数删除K个数字，使剩下的数字串最小

使用贪心算法来解决：

1. 分解为每次删除1位数字，删除k次，每次都要求删除后的数字串最小
2. 删除出现的第一个左边>右边的数，删除之后高位减小，因为留下的数总是当前最优解
3. 执行k次，得到全局最优解

//删除k个字符，使保留的的数字串最小
func solutionNK(number int, k int) string {
    numberStr := strconv.Itoa(number)
    numbers := []rune(numberStr)
    oriLen := len(numbers)
    flag := true
    //删除k次，每次删除第一次逆序的数字
    for i := 0; i < k; i++ {
        flag = true
        for i := 0; i < len(numbers)-1; i++ {
            num1, _ := strconv.Atoi(string(numbers[i]))
            num2, _ := strconv.Atoi(string(numbers[i+1]))
            if num1 > num2 {
                //删除i
                numbers = append(numbers[:i], numbers[i+1:]...)
                flag = false
                break
            }
        }
        if flag {
            break
        }
    }
    //如果所有数字递增，则删除最后几个数字直接返回
    numbers = numbers[:oriLen-k]
    return string(numbers)
}

贪心算法的证明

https://blog.csdn.net/weixin_34342207/article/details/86877529

反例：

1 路径规划问题

image.png

但是，这种贪心的选择方式，最终求的路径并不是最短路径，因为路径 S->B->D->T 才是最短路径。
为什么贪心算法在这个问题上不工作了呢？
前面的选择，会影响后面的选择。
如果我们第一步从顶点 S 走到顶点 A，那接下来面对的顶点和边，跟第一步从顶点 S 走到顶点 B，是完全不同的。所以，即便我们第一步选择最优的走法（边最短），但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。

2 钱币找零

这个问题在我们的日常生活中更加普遍。假设我们有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币，它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付 K 元，最少要用多少张纸币呢？

找零问题是不是都可以用贪心算法？

反例：考虑币值为100，99和1的币种，每种各一百张，找396元。动态规划可求出四张99元，但贪心算法解出需三张一百和96张一元。

怎样的币值可以用贪心算法进行找零