贪心算法是一种在每一步选择中都采取当前状态下最优的选择，从而希望导致全局最优解的算法策略。

一、基本概念

1.1贪心算法的核心思想

将问题分解为若干个子问题，对每个子问题求解局部最优解，将所有局部最优解组合成原问题的解。

1.2贪心算法的特点

局部最优选择：每一步都做出当前看起来最佳的选择；

不可回退：一旦做出选择就不再改变；

高效性：通常比其他算法（如动态规划）更高效；

不保证全局最优：不一定能得到全局最优解，但对某些问题确实能得到最优解。

1.3适用贪心算法的问题

贪心选择性质：通过局部最优选择能够达到全局最优;

最优子结构：问题的最优解包含其子问题的最优解。

1.4经典贪心算法示例

找零钱问题:

def coin_change(coins, amount):

    coins.sort(reverse=True)

    count = 0

    for coin in coins:

        while amount >= coin:

            amount -= coin

            count += 1

    return count if amount == 0 else -1

活动选择问题:

def activity_selection(start, finish):

    activities = list(zip(start, finish))

    activities.sort(key=lambda x: x[1])  # 按结束时间排序

    selected = [activities[0]]

    for current in activities[1:]:

        if current[0] >= selected[-1][1]:

            selected.append(current)

    return selected

霍夫曼编码:

import heapq

def build_huffman_tree(frequencies):

    heap = [[weight, [symbol, ""]] for symbol, weight in frequencies.items()]

    heapq.heapify(heap)

    while len(heap) > 1:

        lo = heapq.heappop(heap)

        hi = heapq.heappop(heap)

        for pair in lo[1:]:

            pair[1] = '0' + pair[1]

        for pair in hi[1:]:

            pair[1] = '1' + pair[1]

        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

    return heap[0][1:]

二、贪心算法的证明及局限

2.1证明

贪心选择性质证明：证明贪心选择是安全的;

最优子结构证明：证明问题具有最优子结构;

数学归纳法：通过归纳法证明贪心选择的正确性。

2.2局限性

不能解决所有优化问题；

对于某些问题，贪心策略只能得到近似解而非最优解，需要仔细分析问题是否适合贪心策略；

三、贪心vs动态规划

特性：贪心算法|动态规划

决策|每个阶段做出一个不可更改的决策|每个阶段依赖前面的决策

最优性：不一定全局最优|保证全局最优

效率：通常更高效|通常需要更多时间和空间

子问题重叠：无|有

记忆化：不需要|通常需要

贪心算法是算法设计中一个简单而强大的工具，适用于特定类型的问题。正确应用贪心策略可以高效地解决许多实际问题。