贪心算法概述

贪心算法（又称贪婪算法），基本原理是，遵循某种既定原则，不断地选取当前条件下最优的选择来构造每一个子步骤，直到获得问题最终的求解。即在求解时，总是作出当前看来最好的选择。也就是说，不从整体最优上加以考虑，仅是求解局部最优解，以期望能找到全局最优解。

贪心算法与动态规划类似，都是将原来的较大规模的问题拆分为规模较小的问题，依据大问题与小问题之间的递推关系，通过解决较小规模的问题，最终获得原始问题的求解。但是动态规划要通盘考虑各个阶段各子问题的求解情况，从全局的角度进行衡量，最终找到解决原始问题的最佳解决方案。贪心算法与动态规划的不同之处在于，贪心算法利用问题的贪心性质，简化了分解原始问题的过程，每次只关注在当前状态下可以获得的局部最优解，通过拼接各阶段的局部最优解获得最终问题的解。因为贪心选择可以依赖于以往所做的选择，但绝不依赖于未来所做的选择，也不依赖于子问题的解。故而贪心算法往往求解时与动态规划相反，采用自顶向下的方式，迭代作出贪心选择，不断化简问题规模。

利用贪心算法解题，需要解决两个问题：

• 是否适合用贪心法求解，即所求解问题是否具有贪心选择性质。所谓贪心选择性质是指应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。贪心选择性质的证明一般采用数学归纳法，证明每一步做出的贪心选择确实能导致问题的整体（全局）最优解，也有基于算法的输出，或使用一种“拟阵”结构等形式的证明。
• 是否具有局部最优解，从而通过选择一个贪心标准，可以得到问题的最优解。贪心算法和动态规划都依赖于问题具有最优子结构性质，但并不是具有最优子结构性质的问题就可以用贪心算法求解。贪心算法不是总能对动态规划求解最优化问题进行优化的。

贪心算法解题思路

1. 建立对问题精确描述的数学模型，包括定义最优解的模型；
2. 将问题分成一系列的子问题，同时定义子问题的最优解结构；
3. 应用贪心算法原则可以确定每个子问题的局部最优解，并根据最优解模型，用子问题的局部最优解堆叠出全局最优解。

代码示例

• 硬币找零问题是给定找零金额，计算如何搭配使得使用的硬币数量最少

# 硬币找零问题是给定找零金额，计算如何搭配使得使用的硬币数量最少
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]))

哈夫曼树：

总结

• 贪心算法需要具备贪心选择性质和最优子结构性质
• 动态规划和贪心算法的计算顺序是相反的，动态规划由下而上，贪心从顶而下；