概述
貪心算法（英語：greedy algorithm）茫多，又稱貪婪算法盲镶，是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的算法
貪心算法解決問題的正確性雖然很多時(shí)候都看起來是顯而易見的仰剿，但是要嚴(yán)謹(jǐn)?shù)刈C明算法能夠得到最優(yōu)解全陨，并不是件容易的事。所以甚颂，很多時(shí)候蜜猾，我們只需要多舉幾個(gè)例子，看一下貪心算法的解決方案是否真的能得到最優(yōu)解就可以了振诬。
適用情況
貪心法可以解決一些最優(yōu)化問題蹭睡，如：求圖中的最小生成樹、求哈夫曼編碼……對(duì)于其他問題赶么，貪心法一般不能得到我們所要求的答案肩豁。一旦一個(gè)問題可以通過貪心法來解決，那么貪心法一般是解決這個(gè)問題的最好辦法辫呻。由于貪心法的高效性以及其所求得的答案比較接近最優(yōu)結(jié)果清钥，貪心法也可以用作輔助算法或者直接解決一些要求結(jié)果不特別精確的問題。
貪心算法的2個(gè)條件：
最優(yōu)子結(jié)構(gòu)性質(zhì)
如果一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解放闺，我們就稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)循捺。
貪心選擇性質(zhì)
對(duì)于某個(gè)問題，如果我們可以通過做出局部最優(yōu)（貪心）選擇來構(gòu)造全局最優(yōu)解雄人，那么我們就稱該問題具有貪心選擇性質(zhì)。
基本步驟
第一步，當(dāng)我們看到這類問題的時(shí)候础钠，首先要聯(lián)想到貪心算法：針對(duì)一組數(shù)據(jù)恰力，我們定義了限制值和期望值，希望從中選出幾個(gè)數(shù)據(jù)旗吁，在滿足限制值的情況下踩萎，期望值最大。
第二步很钓，我們嘗試看下這個(gè)問題是否可以用貪心算法解決：每次選擇當(dāng)前情況下香府，在對(duì)限制值同等貢獻(xiàn)量的情況下，對(duì)期望值貢獻(xiàn)最大的數(shù)據(jù)码倦。
第三步企孩，我們舉幾個(gè)例子看下貪心算法產(chǎn)生的結(jié)果是否是最優(yōu)的。
大部分情況下袁稽，舉幾個(gè)例子驗(yàn)證一下就可以了勿璃。嚴(yán)格地證明貪心算法的正確性，是非常復(fù)雜的推汽，需要涉及比較多的數(shù)學(xué)推理补疑。而且，從實(shí)踐的角度來說歹撒，大部分能用貪心算法解決的問題莲组，貪心算法的正確性都是顯而易見的，也不需要嚴(yán)格的數(shù)學(xué)推導(dǎo)證明暖夭。
實(shí)戰(zhàn)分析
1 分糖果
我們有 m 個(gè)糖果和 n 個(gè)孩子锹杈。我們現(xiàn)在要把糖果分給這些孩子吃，但是糖果少鳞尔，孩子多（m<n）嬉橙，所以糖果只能分配給一部分孩子。 每個(gè)糖果的大小不等寥假，這 m 個(gè)糖果的大小分別是 s1市框，s2，s3糕韧，……枫振，sm。除此之外萤彩，每個(gè)孩子對(duì)糖果大小的需求也是不一樣的粪滤，只有糖果的大小大于等于孩子的對(duì)糖果大小的需求的時(shí)候，孩子才得到滿足雀扶。假設(shè)這 n 個(gè)孩子對(duì)糖果大小的需求分別是 g1杖小，g2肆汹，g3，……予权，gn昂勉。
我的問題是，如何分配糖果扫腺，能盡可能滿足最多數(shù)量的孩子岗照？
問題抽象：從 n 個(gè)孩子中，抽取一部分孩子分配糖果笆环，讓滿足的孩子的個(gè)數(shù)（期望值）是最大的攒至。這個(gè)問題的限制值就是糖果個(gè)數(shù) m。
使用貪心算法來解決：
- 對(duì)于一個(gè)孩子來說躁劣，如果小的糖果可以滿足迫吐，我們就沒必要用更大的糖果。
- 另一方面习绢，對(duì)糖果大小需求小的孩子更容易被滿足渠抹，所以，我們可以從需求小的孩子開始分配糖果闪萄。
- 因?yàn)闈M足一個(gè)需求大的孩子跟滿足一個(gè)需求小的孩子梧却，對(duì)我們期望值的貢獻(xiàn)是一樣的。
- 我們每次從剩下的孩子中败去，找出對(duì)糖果大小需求最小的放航，然后發(fā)給他剩下的糖果中能滿足他的最小的糖果，這樣得到的分配方案圆裕，也就是滿足的孩子個(gè)數(shù)最多的方案广鳍。
2 區(qū)間覆蓋問題
假設(shè)我們有 n 個(gè)區(qū)間，區(qū)間的起始端點(diǎn)和結(jié)束端點(diǎn)分別是 [l1, r1]吓妆，[l2, r2]赊时，[l3, r3]，……行拢，[ln, rn]祖秒。我們從這 n 個(gè)區(qū)間中選出一部分區(qū)間，這部分區(qū)間滿足兩兩不相交（端點(diǎn)相交的情況不算相交）舟奠，最多能選出多少個(gè)區(qū)間呢竭缝？
類似場景：任務(wù)調(diào)度、教師排課
問題抽象：
- 從n個(gè)區(qū)間中沼瘫，滿足兩兩不相交
- 區(qū)間的個(gè)數(shù)（期望值）是最大的抬纸。
使用貪心算法來解決：
- 將所有區(qū)間從左至右排列
- 子問題：讓達(dá)到一個(gè)期望(得到一個(gè)不相交區(qū)間)時(shí)，rx所在位置盡可能靠左（因?yàn)楹罄m(xù)區(qū)間越容易滿足不相交）耿戚。則rx 即為當(dāng)前期望下rx的最優(yōu)解湿故。
3 霍夫曼編碼
假設(shè)我有一個(gè)包含 1000 個(gè)字符的文件阿趁，每個(gè)字符占 1 個(gè) byte（1byte=8bits），?存儲(chǔ)這 1000 個(gè)字符就一共需要 8000bits晓锻，那有沒有更加節(jié)省空間的存儲(chǔ)方式呢歌焦？
問題抽象：
- 總的字符加權(quán)和最小（字符*頻率加和）
使用貪心算法來解決：
- 頻率高的占用字符盡可能少
image.png
霍夫曼樹動(dòng)態(tài)創(chuàng)建過程：
霍夫曼樹動(dòng)態(tài)創(chuàng)建過程演示
定義霍夫曼樹結(jié)構(gòu)
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
}
實(shí)現(xiàn)優(yōu)先隊(duì)列砚哆，使用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] }
構(gòu)建霍夫曼樹
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]
}
}
運(yùn)行測試
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{})
}
輸出結(jié)果：
=== 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位數(shù)刪除K個(gè)數(shù)字，使剩下的數(shù)字串最小
使用貪心算法來解決：
- 分解為每次刪除1位數(shù)字屑墨，刪除k次躁锁，每次都要求刪除后的數(shù)字串最小
- 刪除出現(xiàn)的第一個(gè)左邊>右邊的數(shù)，刪除之后高位減小卵史，因?yàn)榱粝碌臄?shù)總是當(dāng)前最優(yōu)解
- 執(zhí)行k次战转，得到全局最優(yōu)解
//刪除k個(gè)字符，使保留的的數(shù)字串最小
func solutionNK(number int, k int) string {
numberStr := strconv.Itoa(number)
numbers := []rune(numberStr)
oriLen := len(numbers)
flag := true
//刪除k次以躯，每次刪除第一次逆序的數(shù)字
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
}
}
//如果所有數(shù)字遞增槐秧，則刪除最后幾個(gè)數(shù)字直接返回
numbers = numbers[:oriLen-k]
return string(numbers)
}
貪心算法的證明
https://blog.csdn.net/weixin_34342207/article/details/86877529
反例：
1 路徑規(guī)劃問題
但是，這種貪心的選擇方式忧设，最終求的路徑并不是最短路徑刁标，因?yàn)槁窂?S->B->D->T 才是最短路徑。
為什么貪心算法在這個(gè)問題上不工作了呢址晕？
前面的選擇膀懈，會(huì)影響后面的選擇。
如果我們第一步從頂點(diǎn) S 走到頂點(diǎn) A谨垃，那接下來面對(duì)的頂點(diǎn)和邊启搂，跟第一步從頂點(diǎn) S 走到頂點(diǎn) B，是完全不同的刘陶。所以胳赌，即便我們第一步選擇最優(yōu)的走法（邊最短），但有可能因?yàn)檫@一步選擇匙隔，導(dǎo)致后面每一步的選擇都很糟糕疑苫，最終也就無緣全局最優(yōu)解了。
2 錢幣找零
這個(gè)問題在我們的日常生活中更加普遍牡直。假設(shè)我們有 1 元缀匕、2 元、5 元碰逸、10 元乡小、20 元、50 元饵史、100 元這些面額的紙幣满钟，它們的張數(shù)分別是 c1胜榔、c2、c5湃番、c10夭织、c20、c50吠撮、c100尊惰。我們現(xiàn)在要用這些錢來支付 K 元，最少要用多少張紙幣呢泥兰？
找零問題是不是都可以用貪心算法弄屡？
反例：考慮幣值為100，99和1的幣種鞋诗，每種各一百張膀捷，找396元。動(dòng)態(tài)規(guī)劃可求出四張99元削彬，但貪心算法解出需三張一百和96張一元全庸。
