贪心算法介绍（Greedy Algorithm）

贪心算法介绍（Greedy Algorithm）

1. 贪心算法概念简介

​ 贪心算法Greedy Algorithm是一种在每一步选择中都采取当前状态下最优（或最有利）决策的算法策略，以期望通过这样的局部最优决策达到全局最优解。它适用于那些具有最优子结构的问题，即问题的最优解包含其子问题的最优解。贪心算法的关键在于它做出的选择是不可逆的，一旦选择了某个选项，就不会再回溯考虑其他选项。

• 通过示例来感受贪心算法的思想

有一堆不同大小的饼干，大小分别为 1, 3, 2, 4, 5。而面前有一群孩子，胃口也不一样。每个孩子的胃口代表了他们最小能接受的饼干大小，比如说，有的孩子最少要吃一个大小为 3 的饼干才能满足。

目标是尽可能多地满足孩子们的胃口。

饼干大小：3, 2, 1, 4, 5

孩子胃口：3, 2, 4

• 贪心算法的过程

1. 排序：将饼干和孩子的胃口从小到大排序。

   • 饼干：1, 2, 3, 4, 5
   • 孩子：2, 3, 4

2. 逐步计算选择最小的满足：

   • 第一个孩子胃口为 2，直接选择大小为 2 的饼干满足他。
   • 第二个孩子胃口为 3，直接选择大小为 3 的饼干满足他。
   • 第三个孩子胃口为 4，直接选择大小为 4 的饼干满足他。

3. 结果：你成功地满足了 3 个孩子。贪心算法通过每一步都做出当前看起来最好的选择（用最小的饼干去满足最小的胃口），得出了一个不错的结果。

使用非贪心算法的思维来解决的方式

• 动态规划的过程（非贪心算法）

1. 状态定义：

   • 创建一个二维数组 dp[i][j]，表示用前 i 个饼干去满足前 j 个孩子能达到的最大满足数。

2. 初始化：

   • dp[0][0] = 0 表示没有饼干和没有孩子时，满足的孩子数为 0。

3. 状态转移：

   • 当不使用当前饼干：dp[i][j] = dp[i-1][j]
   • 当使用当前饼干（前提是饼干大小满足孩子的胃口）：dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + 1)

4. 逐步计算：

   • 用第一个饼干（大小为 1），不能满足任何孩子，所以 dp[1][j] = 0 对于所有 j。
   • 用第二个饼干（大小为 2），可以满足第一个孩子，更新 dp[2][1] = 1。
   • 用第三个饼干（大小为 3），可以满足第二个孩子，更新 dp[3][2] = 2。
   • 用第四个饼干（大小为 4），可以满足第三个孩子，更新 dp[4][3] = 3。
   • 用第五个饼干（大小为 5），没有其他孩子可以满足，但可以继续保持 dp[5][3] = 3。

5. 结果：最终，dp[5][3] = 3 表示最多可以满足 3 个孩子。

• 对比分析

  • 贪心算法：

    • 思路：每一步选择当前最优解，不考虑未来可能性。
    • 优点：计算速度快，适合简单或可以局部最优逼近全局最优的问题。
    • 结果：在这个例子中，贪心算法直接选择合适的饼干来满足每个孩子，最终结果为 3 个孩子满足。

  • 动态规划：

    • 思路：通过记录之前的计算结果，考虑所有可能的情况来构建全局最优解。
    • 优点：能够找到全局最优解，适合复杂问题。
    • 结果：动态规划考虑了所有可能的分配方式，得到了最大可能的 3 个孩子满足。

虽然在这个例子中，贪心算法和动态规划的结果相同，但贪心算法只在局部做出最优选择，不保证全局最优。而动态规划通过全面分析，确保找到了全局最优解。动态规划的计算更复杂，但适用于需要全局最优解的问题。

2. 贪心算法的特点

1. 贪心选择性质：

   • 贪心算法在每一步都做出当前看起来最优的选择，而不考虑这个选择对未来步骤的影响。这种选择是基于问题的贪心选择性质，即问题具有这样的结构：局部最优选择可以导致全局最优解。

2. 无回溯：

   • 与动态规划等其他算法不同，贪心算法做出选择后不会回溯。这意味着一旦做出了一个贪心选择，算法就会继续前进，即使这个选择在后来看起来可能不是最佳选择。

     贪心算法的不回溯特性强调了算法的确定性和一次性，每次选择都是最终的，不依赖于未来的信息，也不考虑撤销或修改之前的选择。这种特性使得贪心算法在某些问题上非常高效，但在其他问题上可能需要更复杂的算法来确保找到全局最优解。

3. 子问题局部最优：

   • 贪心算法通常用于具有最优子结构的问题，即一个问题的最优解包含其子问题的最优解。这种特性允许算法在构建解决方案的过程中，利用子问题的局部最优解。

4. 简单高效：

   • 贪心算法通常易于理解和实现，因为它的决策过程直观且不需要复杂的优化过程。此外，由于贪心算法不需要存储所有可能的解决方案，因此它在空间复杂度上通常很低。

5. 不保证全局最优：

   • 尽管贪心算法在某些问题上能够找到全局最优解，但它并不保证在所有情况下都能找到。这取决于问题本身是否满足贪心选择性质和最优子结构。

3. 贪心算法的应用场景

• 物流优化：在物流配送中，使用贪心算法来规划最短或最快路径，例如快递员的包裹派送顺序，以减少行驶距离和时间 。

贪心算法在物流优化中的应用主要体现在配送路径的选择上。其核心原理是每一步都选择当前状态下的最优决策，以期望最终得到全局的最优解。在物流配送系统中，这通常意味着选择最短或成本最低的配送路径，以达到节省时间和成本的目的。

具体来说，贪心算法在物流配送中的优化原理可以这样理解：假设一个快递员需要配送多个包裹到不同的地点，使用贪心算法，快递员会先选择最近的一个配送点进行配送，完成后再选择下一个最近的点，依此类推，直到所有的配送任务完成。这种方法简单快捷，能够快速得到一个近似的最优解，尽管这个解可能不是绝对最优的 。

• 网络路由选择：在计算机网络中，通过贪心算法选择数据传输的最优路径，例如OSPF（开放最短路径优先）协议 。

贪心算法在网络路由选择中的应用主要是基于其局部最优策略来实现快速决策。在网络路由选择中，贪心算法可以帮助路由器选择到目的地的最短路径或者成本最低的路径。其基本原理是，在每个决策点上，路由器会根据当前可用的信息，选择一条看似最优的路径，而不考虑这条路径对后续路由选择的影响 。

在实际的网络协议中，OSPF（Open Shortest Path First）是一个广泛应用的链路状态路由协议，它使用Dijkstra算法来计算最短路径树，从而确定到达每个目的地的最佳路径 。OSPF协议能够快速响应网络拓扑的变化，并且计算出的路由路径较为优化 。

贪心算法并不总是能够得到全局最优解。在某些情况下，例如在存在环路或者路径成本突然增加的场景下，贪心算法可能会陷入次优解。因此，在设计路由算法时，需要考虑网络的具体特点和需求，结合其他算法或机制来确保路由的稳定性和效率

• 任务调度：在计算机系统中，贪心算法用于CPU任务调度，选择优先级最高或最早截止时间的任务先执行 。

贪心算法在任务调度领域的应用原理是选择当前最优的任务进行执行，以期望通过局部最优选择累积达到全局的优化目标。这种策略通常涉及对任务列表按照特定标准（如最短执行时间、最晚截止时间或最高优先级）进行排序，然后依次考虑每个任务，根据当前资源状态和约束条件决定是否执行该任务。贪心算法的决策过程是即时的，不涉及对过去选择的回溯，这使得算法在很多情况下能够快速得到一个可行的解决方案，尽管这不一定是绝对最优的。

• 数据压缩：霍夫曼编码是一种使用贪心算法的数据压缩技术，通过为频繁出现的字符分配较短的编码来优化存储空间 。

贪心算法在数据压缩中的应用主要是通过霍夫曼编码（Huffman Coding）实现的。霍夫曼编码是一种非常有效的数据压缩技术，它利用了贪心算法来为数据中的每个字符分配一个变长的编码，其中出现频率高的字符被分配较短的编码，而出现频率低的字符被分配较长的编码，从而实现整体数据的压缩 。

霍夫曼编码的实现原理基于构建一棵霍夫曼树，这棵树是通过一个由字符出现频率决定的优先队列构建的。算法从队列中取出频率最小的两个节点，将它们合并为一个新节点，新节点的频率是这两个节点频率之和，这个过程不断重复，直到队列中只剩下一个节点，这个节点就是霍夫曼树的根节点 。

在构建霍夫曼树的过程中，树中的每个左节点对应一个’0’编码，每个右节点对应一个’1’编码。从根节点到叶节点的路径就形成了字符的霍夫曼编码。由于霍夫曼编码要求任何编码都不是其他编码的前缀，这样可以保证解码时不会出现歧义 。

使用霍夫曼编码进行数据压缩的过程可以显著减少数据的存储空间，压缩率通常在20%到90%之间，这取决于数据的特性。霍夫曼编码不仅考察了文本中不同字符的数量，还考虑了每个字符出现的频率，通过这种方式，霍夫曼编码实现了数据的有效压缩

• 股票交易分析：在金融领域，贪心算法可以用来模拟股票买卖，选择最优的买入和卖出时机以最大化利润 。

贪心算法在股票交易策略中的应用是利用局部最优决策来实现利润最大化。它通过跟踪股票价格变动，在价格低点买入并在高点卖出，以此累积利润。同时，算法会考虑交易成本如手续费，并适应市场规则，例如交易冷冻期和交易次数限制。贪心算法的实现简单高效，适合快速变化的股票市场，尽管它不保证全局最优，但通常能够获得接近最优的交易结果。

• 广告投放：在广告行业，通过贪心算法优化广告投放策略，选择最有效的广告组合和展示顺序以吸引用户 。

贪心算法在广告投放领域的应用主要体现在对广告展示机会的优化分配上。具体来说，广告系统需要在多个广告主的合约中做出选择，以确保每个广告主都能获得合约中规定的曝光量，同时还要考虑到曝光的时间分布，避免广告在短期内过度集中展示 。这种分配问题可以视为一个优化问题，其中贪心算法因其简单高效的特性而被广泛应用。

在广告投放中，贪心算法的一个典型应用是解决合约制广告的在线分配问题。这类问题通常涉及到大量的广告主合约和流量，算法需要在保证所有合约完成的同时，尽可能地满足广告主对曝光量和时间分布的要求。贪心算法通过在每次曝光机会出现时，选择当前最优的广告主进行展示，从而实现对广告流量的动态分配 。

贪心算法还可以用于处理广告投放中的其他优化问题，如广告位的分配、广告内容的个性化推荐等。在这些场景中，贪心算法通过在每一步选择中采取当前最优的决策，以达到整体的优化目标

4. 贪心算法的优缺点

• 优点

1. 简单高效：贪心算法通常易于理解和实现，执行速度快，不需要复杂的优化过程。
2. 快速得到解决方案：贪心算法能够迅速给出问题的解决方案，对于需要即时决策的问题特别有用。
3. 空间效率高：由于其决策过程不需要存储所有可能的解决方案，因此空间复杂度通常较低。
4. 适应性广：贪心算法可以应用于多种问题领域，如资源分配、路径选择、任务调度等。
5. 启发式方法：作为一种启发式算法，贪心算法用于快速找到一个可接受的解决方案，而不是总是寻找最优解。

• 缺点

1. 不保证全局最优：贪心算法在某些情况下可能无法得到全局最优解，特别是当问题不具有贪心选择性质时。
2. 依赖于问题结构：贪心算法的成功依赖于问题是否具有最优子结构，对于不具备这种结构的问题可能不适用。
3. 可能错过更优解：由于贪心算法的决策是不可逆的，一旦做出选择就不再回溯，可能会错过更优的解决方案。
4. 局限性：对于一些NP难问题，贪心算法可能只能得到局部最优解，而不是绝对最优解。
5. 需要问题证明：在使用贪心算法时，需要证明其正确性，这可能需要一些数学推理和证明工作。

5. 贪心算法的实现步骤

1. 明确问题：

   • 确定你要解决的问题是什么，比如分配资源、选择任务、规划路径等。

2. 理解贪心选择：

   • 找出问题中可以应用贪心选择的地方，即在每一步选择中都采取当前看起来最好的决策。

3. 设定目标：

   • 确定你的“贪心目标”是什么，也就是你希望通过贪心选择达到什么样的效果，比如最小化成本、最大化利润等。

4. 准备数据：

   • 收集并准备所有需要的数据，比如资源数量、任务列表、路径信息等。

5. 排序或组织数据：

   • 根据你的目标，可能需要对数据进行排序或以某种方式组织，以便贪心选择可以更容易进行。

6. 执行贪心策略：

   • 从第一步开始，每次都选择当前看起来最佳的选项。例如，如果你的目标是最小化成本，那么就选择成本最低的选项。

7. 更新选择状态：

   • 每次做出选择后，更新当前的状态，这可能意味着从可用选项中移除已选择的选项，或者更新剩余资源的数量。

8. 重复选择过程：

   • 继续执行贪心选择，直到所有的选项都被选择完，或者达到某个特定的条件。

9. 检查结果：

   • 完成所有步骤后，检查你的结果是否满足问题的要求。

10. 评估和调整：

    • 如果结果不是预期的，可能需要回到前面的步骤，调整你的贪心策略或选择标准。

举个例子，如果要用贪心算法来安排一天的工作，步骤可能是这样的：

• 确定你要完成的所有工作任务。
• 决定你的贪心目标，比如完成最多的任务或完成最重要的任务。
• 列出每个任务需要的时间和重要性。
• 根据任务的紧急程度或重要性对任务进行排序。
• 从列表的顶部开始，逐个选择任务，并安排到你的日程中。
• 每次选择后，更新你的日程表，直到所有任务都被安排或时间被填满。
• 最后，检查你的日程表，确保所有任务都已妥善安排。

6. 贪心算法与其他算法的比较

7. 贪心算法的示例演示

示例1：分糖果问题

简介：有一组孩子的胃口值 g 和一组糖果的大小 s，我们要尽量多的满足孩子。每个孩子只能拿到一个糖果，且只有当糖果的大小大于或等于孩子的胃口值时，孩子才能满足。

思维过程：

1. 目标：最大化能满足的孩子数量。
2. 贪心选择：每次优先满足胃口最小的孩子，因为大胃口的孩子可以用大糖果来满足，但小胃口的孩子需要较小的糖果。
3. 步骤分析：
   • 首先对孩子的胃口和糖果的大小进行排序，以便从最小的胃口和最小的糖果开始比较。
   • 然后，逐一遍历糖果，尝试将糖果分给胃口最小的孩子。
   • 如果糖果能够满足当前孩子，就给这个孩子糖果，并继续考虑下一个孩子。
   • 最后，统计并返回能够满足的孩子数量。

def findContentChildren(g, s):
    # 对孩子的胃口和糖果大小进行排序
    g.sort()
    s.sort()

    # 用于统计能够满足的孩子数量
    child_i = 0

    # 遍历每个糖果的大小
    for size in s:
        # 如果当前孩子的胃口能被满足
        if child_i < len(g) and size >= g[child_i]:
            child_i += 1  # 孩子得到了糖果

    # 返回能够满足的孩子数量
    return child_i


# 测试
g = [1, 2, 5, 4, 3, 666]  # 孩子的胃口值
s = [1, 2, 1, 1]  # 糖果的大小
print(findContentChildren(g, s))  # 输出: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

胃口 g = [1, 2, 5, 4, 3, 666] 排序 -> [1, 2, 3, 4, 5, 666]

糖果 s = [1, 2, 1, 1] 排序 -> [1, 1, 1, 2]

糖果s[1]->g[1] +1

糖果s[1 ,1] -> g[2] +1

剩下糖果不满足于孩子的胃口值，通过贪心算法，我们总是优先满足胃口最小的孩子，这样能使得最多的孩子得到糖果

示例2：零钱兑换问题

简介：给定一些硬币面值 coins 和一个目标金额 amount，找到能够凑成该金额的最少硬币数。

思维过程：

1. 目标：最小化使用的硬币数量。
2. 贪心选择：每次选择面值最大的硬币，这样可以尽快减少剩余的金额，减少所需的硬币数量。
3. 步骤分析：
   • 将硬币按面值从大到小排序，以便优先使用大面值的硬币。
   • 依次从最大的硬币开始，计算该硬币可以使用多少次，减少目标金额。
   • 剩余金额用更小面值的硬币继续凑。
   • 最后，如果能完全凑成目标金额，就返回硬币数量；否则返回 -1。

def coinChange(coins, amount):
    # 将硬币面值从大到小排序
    coins.sort(reverse=True)
    count = 0  # 统计使用的硬币数量

    # 遍历每种面值的硬币
    for coin in coins:
        if amount == 0:  # 如果金额已经为0，停止
            break
        count += amount // coin  # 使用最大面值硬币的最大数量
        amount %= coin  # 更新剩余金额

    # 如果金额能够被完全兑换，返回硬币数量，否则返回-1
    return count if amount == 0 else -1


# 测试
coins = [1, 2, 5]  # 硬币面值
amount = 11  # 目标金额
print(coinChange(coins, amount))  # 输出: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

通过每次选择最大的硬币，我们可以尽快减少目标金额，达到使用最少硬币的目的。

11->(5,5,1)

示例3：区间调度问题

简介：给定一组时间区间 intervals，找出最多的互不重叠的区间数。例如，多个会议时间重叠的情况下，最多能够安排多少场不冲突的会议。

思维过程：

1. 目标：最大化选择的区间数量。
2. 贪心选择：每次选择结束时间最早且与前一个区间不重叠的区间，这样可以给后续的区间留出更多的时间。
3. 步骤分析：
   • 首先按区间的结束时间进行排序，以便优先考虑结束时间早的区间。
   • 从第一个区间开始，选择它作为第一个非重叠区间，并记录它的结束时间。
   • 依次考虑后续的区间，如果它的开始时间不早于前一个区间的结束时间，就选择这个区间，并更新结束时间。
   • 最后，返回选择的区间数量。

def intervalSchedule(intervals):
    # 根据区间的结束时间进行排序
    intervals.sort(key=lambda x: x[1])
    count = 0  # 统计能够安排的区间数量
    end = float('-inf')  # 记录上一个选择的区间的结束时间

    # 遍历所有区间
    for interval in intervals:
        if interval[0] >= end:  # 如果当前区间的开始时间大于等于上一个区间的结束时间
            count += 1  # 选择当前区间
            end = interval[1]  # 更新结束时间

    # 返回能够安排的最大区间数量
    return count


# 测试
intervals = [[1, 3], [2, 4], [3, 5]]  # 时间区间
print(intervalSchedule(intervals))  # 输出: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

通过每次选择结束时间最早的区间，能够留下更多的时间给后面的区间，从而选择尽可能多的

[1, 3], [2, 4]区间重叠, [3, 5] -> [1, 3], [3, 5] -> 2

示例4：分配会议室问题

简介：给定一组会议的开始和结束时间intervals，找出需要的最少会议室数量，以确保所有会议都能安排上。

思维过程：

1. 目标：最小化同时进行的会议数（即需要的会议室数）。
2. 贪心选择：每次安排一个会议时，检查最早结束的会议是否已经结束，如果结束了就可以复用该会议室，否则需要新开一个会议室。
3. 步骤分析：
   • 先将所有会议按开始时间排序。
   • 使用一个最小堆来跟踪当前所有正在进行的会议的结束时间。
   • 对于每个会议，如果它的开始时间不早于最早结束的会议的结束时间，则表示可以复用一个会议室，更新堆中的结束时间。
   • 否则，需要新开一个会议室，将会议的结束时间加入堆中。
   • 最后，堆的大小就是需要的最少会议室数量。

import heapq


def minMeetingRooms(intervals):
    if not intervals:
        return 0

    # 根据会议的开始时间进行排序
    intervals.sort(key=lambda x: x[0])

    # 初始化一个最小堆，用于存储当前进行的会议的结束时间
    heap = []
    heapq.heappush(heap, intervals[0][1])  # 将第一个会议的结束时间加入堆中

    # 遍历剩余的会议
    for i in intervals[1:]:
        # 如果当前会议的开始时间大于等于堆顶的结束时间
        if i[0] >= heap[0]:
            heapq.heappop(heap)  # 移除堆顶的会议，因为它已经结束了
        heapq.heappush(heap, i[1])  # 将当前会议的结束时间加入堆中

    # 最后堆的大小就是需要的会议室数量
    return len(heap)


# 测试
intervals = [[0, 30], [5, 10], [15, 20], [5, 20], [35, 40]]  # 会议时间区间
print(minMeetingRooms(intervals))  # 输出: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

使用最小堆动态管理会议的结束时间，通过贪心选择，及时释放已结束的会议室，确保所需的会议室数量最少。

示例5：最大子数组和问题

简介：在一个整数数组 nums 中，找到和最大的连续子数组，并返回其最大和。

思维过程：

1. 目标：找到和最大的连续子数组。
2. 贪心选择：每次都判断是将当前元素加入到之前的子数组中，还是重新开始一个新的子数组，从而保证当前的子数组和尽可能大。
3. 步骤分析：
   • 初始化当前子数组和 current_sum 和最大子数组和 max_sum 为第一个元素。
   • 从第二个元素开始，逐个判断：
     • 当前元素是否比 current_sum + 当前元素 更大。如果是，则抛弃之前的子数组，重新开始；否则将当前元素加入到当前子数组中。
   • 每次更新最大子数组和 max_sum。
   • 最终返回最大子数组和。

def maxSubArray(nums):
    max_sum = nums[0]  # 初始化最大和为数组的第一个元素
    current_sum = nums[0]  # 当前子数组的和

    # 遍历数组的其余元素
    for num in nums[1:]:
        # 如果当前子数组的和加上当前元素还不如当前元素本身大，就丢弃当前子数组，重新开始
        current_sum = max(num, current_sum + num)
        # 更新最大和
        max_sum = max(max_sum, current_sum)

    # 返回最大子数组和
    return max_sum


# 测试
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]  # 输入数组
print(maxSubArray(nums))  # 输出: 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

通过贪心策略，决定是否将当前元素加入到之前的子数组中，从而保证当前的子数组和尽可能大，最终找到全局最大子数组和。

8. 贪心算法的回顾总结

贪心算法是一种在每一步选择中都采取当前最优解的策略，以期望构建出全局最优解的算法。它的核心思想是“贪心选择性质”，即在每个决策点上，基于当前信息选择最有利的选项，从而希望通过这些局部最优决策累积成全局最优解。贪心算法的实现通常简单直接，易于编码，且执行效率高，这使得它在需要快速响应的大规模问题中非常有用。

贪心算法的关键在于其贪心策略的选择，这通常涉及到对问题结构的深入理解。在某些问题中，贪心算法能够保证找到最优解，特别是当问题具有最优子结构和贪心选择性质时。然而，并非所有问题都适合使用贪心算法，有些情况下贪心算法可能只能得到局部最优解而非全局最优解。

贪心算法的一个显著特点是其决策过程是单向的，不会回溯。这意味着一旦做出选择，算法不会重新考虑之前的决策，即使这些决策最终可能不是最佳选择。这种特性使得贪心算法在时间效率上具有优势，但同时也限制了它在某些需要全局考虑的问题上的适用性。

贪心算法广泛应用于资源分配、路径规划、任务调度、数据压缩等领域。例如，在霍夫曼编码中用于数据压缩，在Dijkstra算法中用于寻找单源最短路径。尽管贪心算法在某些情况下可能需要结合其他算法来优化其策略，但其作为一种高效且直观的算法，仍然在算法设计和优化问题解决中占有重要地位。