贪心算法经典问题

贪心算法是解决一类优化问题的有效策略，通过在每一步选择中做出局部最优选择，希望最终能够达到全局最优解。以下是一些经典的贪心算法问题及其应用：

1. 活动选择问题（Activity Selection Problem）

问题描述： 给定一组活动，每个活动有一个开始时间和结束时间，选择尽可能多的活动，使得它们互不重叠。

贪心策略： 每次选择结束时间最早且与已选择活动不冲突的活动。

伪代码：

算法 活动选择(activities)
    按活动的结束时间对活动进行排序
    已选活动集 = []
    上一个活动的结束时间 = 0
    
    对于 每个活动 in activities:
        如果 活动的开始时间 >= 上一个活动的结束时间:
            将活动添加到已选活动集
            更新上一个活动的结束时间为当前活动的结束时间
            
    返回 已选活动集

2. 分数背包问题（Fractional Knapsack Problem）

问题描述： 给定一组物品，每个物品有一个价值和重量，背包有固定的容量，允许对物品进行分割，求能够装入背包的最大价值。

贪心策略： 按单位重量的价值排序，优先选择单位价值最高的物品。

伪代码：

算法 分数背包(items, capacity)
    按物品的价值重量比降序排序
    总价值 = 0
    对于 每个物品 in items:
        如果 物品的重量 <= 背包剩余容量:
            背包剩余容量 -= 物品的重量
            总价值 += 物品的价值
        否则:
            总价值 += 物品的价值 * (背包剩余容量 / 物品的重量)
            跳出循环
    返回 总价值

3. 最小生成树问题（Minimum Spanning Tree, MST）

问题描述： 在一个加权连通图中，找到一个子图，使得它包含所有顶点且边的总权重最小。

贪心策略：

• Kruskal算法：按边的权重从小到大排序，每次选择权重最小且不构成环的边。
• Prim算法：从一个顶点出发，每次选择权重最小且未被访问过的顶点连接的边。

伪代码（Kruskal算法）：

算法 Kruskal(graph)
    初始化一个空集来保存最小生成树(MST)
    按边的权重对所有边进行排序
    对于 每条边 in 排序后的边:
        如果 该边不与MST形成环:
            将该边添加到MST
    返回 MST

伪代码（Prim算法）：

算法 Prim(graph, start_vertex)
    初始化一个优先队列，并将起始顶点加入队列
    初始化一个空集来保存最小生成树(MST)
    当 优先队列不为空:
        提取优先队列中权重最小的顶点
        将该顶点添加到MST
        对于 该顶点的每个邻接顶点:
            如果 邻接顶点不在MST中:
                将该邻接顶点和边权重加入优先队列
    返回 MST

4. 单源最短路径问题（Dijkstra’s Algorithm）

问题描述： 在一个加权图中，找到从源点到所有其他顶点的最短路径。

贪心策略： 每次选择离源点最近的未访问顶点，更新其邻接顶点的最短路径。

伪代码：

算法 Dijkstra(graph, source)
    初始化所有顶点的距离为无穷大，源点距离为0
    初始化一个优先队列，将源点加入队列
    当 优先队列不为空:
        提取优先队列中距离最小的顶点
        对于 提取顶点的每个邻接顶点:
            如果 通过提取顶点的路径比当前已知路径更短:
                更新邻接顶点的距离
                将/更新邻接顶点在优先队列中的位置
    返回 所有顶点的最短距离

5. 霍夫曼编码（Huffman Coding）

问题描述： 对一组字符进行编码，使得编码后的总长度最短，字符出现频率高的使用较短的编码。

贪心策略： 每次选择频率最低的两个字符，合并为一个新的节点，重复直到所有字符被合并到一棵树中。

伪代码：

算法 霍夫曼编码(characters, frequencies)
    初始化一个优先队列，将字符及其频率加入队列
    当 优先队列中有多于一个节点:
        提取两个频率最小的节点
        创建一个新节点，将这两个节点作为子节点，新节点的频率为两子节点频率之和
        将新节点加入优先队列
    返回 优先队列中剩余的唯一节点（霍夫曼树的根节点）

6. 区间调度问题（Interval Scheduling Maximization）

问题描述： 给定一组区间，选择最多的不重叠区间。

贪心策略： 每次选择结束时间最早且不与已选择区间重叠的区间。

伪代码：

算法 区间调度(intervals)
    按区间的结束时间对区间进行排序
    已选区间集 = []
    上一个区间的结束时间 = 0
    
    对于 每个区间 in intervals:
        如果 区间的开始时间 >= 上一个区间的结束时间:
            将区间添加到已选区间集
            更新上一个区间的结束时间为当前区间的结束时间
            
    返回 已选区间集

这些伪代码展示了如何使用贪心算法解决经典问题，通过每一步选择局部最优解来逐步构建最终解。贪心算法的核心在于找到适合当前问题的贪心选择策略，以保证每一步的选择都是局部最优的，希望通过这些局部最优选择来达到全局最优解。