貪心算法概述

貪心算法（又稱貪婪算法），基本原理是，遵循某種既定原則，不斷地選取當前條件下最優的選擇來構造每一個子步驟，直到獲得問題最終的求解。即在求解時，總是作出當前看來最好的選擇。也就是說，不從整體最優上加以考慮，僅是求解局部最優解，以期望能找到全局最優解。

貪心算法與動態規劃類似，都是將原來的較大規模的問題拆分為規模較小的問題，依據大問題與小問題之間的遞推關系，通過解決較小規模的問題，最終獲得原始問題的求解。但是動態規劃要通盤考慮各個階段各子問題的求解情況，從全局的角度進行衡量，最終找到解決原始問題的最佳解決方案。貪心算法與動態規劃的不同之處在于，貪心算法利用問題的貪心性質，簡化了分解原始問題的過程，每次只關注在當前狀態下可以獲得的局部最優解，通過拼接各階段的局部最優解獲得最終問題的解。因為貪心選擇可以依賴于以往所做的選擇，但絕不依賴于未來所做的選擇，也不依賴于子問題的解。故而貪心算法往往求解時與動態規劃相反，采用自頂向下的方式，迭代作出貪心選擇，不斷化簡問題規模。

利用貪心算法解題，需要解決兩個問題：

是否適合用貪心法求解，即所求解問題是否具有貪心選擇性質。所謂貪心選擇性質是指應用同一規則，將原問題變為一個相似的但規模更小的子問題，而后的每一步都是當前看似最佳的選擇。這種選擇依賴于已做出的選擇，但不依賴于未做出的選擇。從全局來看，運用貪心策略解決的問題在程序的運行過程中無回溯過程。貪心選擇性質的證明一般采用數學歸納法，證明每一步做出的貪心選擇確實能導致問題的整體（全局）最優解，也有基于算法的輸出，或使用一種“擬陣”結構等形式的證明。
是否具有局部最優解，從而通過選擇一個貪心標準，可以得到問題的最優解。貪心算法和動態規劃都依賴于問題具有最優子結構性質，但并不是具有最優子結構性質的問題就可以用貪心算法求解。貪心算法不是總能對動態規劃求解最優化問題進行優化的。

貪心算法解題思路

建立對問題精確描述的數學模型，包括定義最優解的模型；
將問題分成一系列的子問題，同時定義子問題的最優解結構；
應用貪心算法原則可以確定每個子問題的局部最優解，并根據最優解模型，用子問題的局部最優解堆疊出全局最優解。

代碼示例

硬幣找零問題是給定找零金額，計算如何搭配使得使用的硬幣數量最少

# 硬幣找零問題是給定找零金額，計算如何搭配使得使用的硬幣數量最少
def get_change(coins, amount):
    coins.sort()
    # 從面值最大的硬幣開始遍歷
    i = len(coins) - 1
    di = {}
    while i >= 0:
        if amount >= coins[i]:
            n = int(amount // coins[i])
            change = n * coins[i]
            amount -= change
            di[coins[i]] = n
        i -= 1
    return di

哈夫曼編碼

現在有一個包含 5 個字符的字符表 {A,B,C,D,E}，各字符出現的頻率A:0.35, B:0.1, C:0.2, D:0.2, E:0.15；

構造一種有效率的編碼類型，使用該編碼表達以上字符表內容時可以產生平均長度最短的位串。在對由 n 個字符組成的文本進行編碼過程中，有兩種編碼方式，即定長編碼和變長編碼。對于定長編碼而言，會為每個字符賦予一個長度固定為 m(m≥log2n) 的位串，我們常用的標準 ASCII 碼就是采用定長編碼策略對字符集進行編碼的。長度各異的編碼，其中出現頻率較高的字符，采用長度較短的編碼表示，出現頻率較低的字符，采用長度較長的編碼表示。

為了對某字母表構造一套二進制的前綴碼，可以借助二叉樹。將樹中所有的左向邊都標記為0，所有的右向邊都標記為 1。通過記錄從根節點到字符所在的葉子節點的簡單路徑上的所有 0-1 標記來獲得表示該字符的編碼。

# 參考文檔: https://www.92Python/ target=_blank class=infotextkey>Python.com/view/354.html
# 樹節點定義
class Node:
    def __init__(self, pro):
        self.left = None
        self.right = None
        self.parent = None
        self.pro = pro

    def is_left(self):  # 判斷左子樹
        return self.parent.left == self

# create nodes創建葉子節點
def create_nodes(pros):
    return [Node(pro) for pro in pros]

# create Huffman-Tree創建Huffman樹
def create_huffman_tree(nodes):
    """從下向上創建二叉樹"""
    queue = nodes[:]
    while len(queue) > 1:
        queue.sort(key=lambda item: item.pro)
        node_left = queue.pop(0)
        node_right = queue.pop(0)
        node_parent = Node(node_left.pro + node_right.pro)  # 二節點值合并
        node_parent.left = node_left  # 父親認兒子，
        node_parent.right = node_right
        node_left.parent = node_parent  # 兒子認父親
        node_right.parent = node_parent
        queue.Append(node_parent)
    queue[0].parent = None
    return queue[0]

# Huffman編碼
def huffman_encoding(nodes, root):
    """根據當前節點為左右子樹進行判斷賦值"""
    codes = [''] * len(nodes)
    for i in range(len(nodes)):
        node_temp = nodes[i]
        while node_temp != root:
            if node_temp.is_left():
                codes[i] = '0' + codes[i]
            else:
                codes[i] = '1' + codes[i]
            node_temp = node_temp.parent  # 當前節點替換為父子節點
    return codes

if __name__ == '__main__':
    letters_pros = [('B', 10), ('E', 15), ('C', 20), ('D', 20), ('A', 35)]
    nodes = create_nodes([item[1] for item in letters_pros])  # 生成樹節點
    root = create_huffman_tree(nodes)
    codes = huffman_encoding(nodes, root)
    for item in zip(letters_pros, codes):
        print('Label:%s pro:%-2d Huffman Code:%s' % (item[0][0], item[0][1], item[1]))

哈夫曼樹：