C++贪心算法

📚 C++ 中贪心算法详解

1. 贪心算法的定义

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下局部最优的选择，以期最终达到全局最优解的算法。

1.1 核心思想

• 局部最优选择：在问题的每一步中，都选择当前看起来最优或最有利的选项。
• 全局最优目标：通过一系列局部最优的选择，最终达到全局最优或近似最优解。
• 不可回溯性：一旦做出选择，无法回头更改之前的选择。

1.2 贪心算法的适用条件

贪心算法并不总能保证得到全局最优解，它只在满足以下两个条件时才适用：

1. 贪心选择性

   • 可以通过每一步的局部最优选择，最终得到全局最优解。

2. 最优子结构

   • 问题的最优解包含其子问题的最优解。

1.3 贪心算法与其他算法的区别

• 动态规划：适合有重叠子问题的场景，结果需要基于多个子问题的解。
• 回溯算法：会考虑所有可能的选择，找到最佳解。
• 贪心算法：在每一步选择中做出最优决定，不再考虑之前的选择或之后的结果。

2. 贪心算法的基本步骤

1. 问题分解：将问题分解为多个子问题。
2. 贪心策略：针对每个子问题，选择当前最优解。
3. 合并结果：将所有子问题的最优解组合起来，形成问题的最终解。
4. 验证结果：判断最终解是否满足问题的要求。

3. 贪心算法的优缺点

✅ 优点：

• 简单直观，易于理解和实现。
• 在某些问题上，可以提供高效的最优解。
• 时间复杂度较低，通常比动态规划更快。

❌ 缺点：

• 并不适用于所有问题，可能无法得到全局最优解。
• 一旦选择某一步，无法回溯进行更改。
• 依赖问题是否满足贪心选择性和最优子结构。

4. 贪心算法的经典应用场景

1. 活动选择问题（Activity Selection Problem）
2. 哈夫曼编码（Huffman Coding）
3. 最小生成树（Minimum Spanning Tree）：Kruskal算法、Prim算法
4. 单源最短路径问题（Shortest Path Problem）：Dijkstra算法
5. 背包问题（Fractional Knapsack Problem）

5. 贪心算法的经典例题

示例：分数背包问题（Fractional Knapsack Problem）

问题描述：

• 有一背包，容量为 ( W )。
• 有 ( n ) 个物品，每个物品有一个重量 ( w_i ) 和价值 ( v_i )。
• 可以将物品切分成任意部分放入背包。
• 目标：在不超过背包容量的前提下，使得背包中的总价值最大化。

贪心策略：

• 优先选择单位价值最高的物品。

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 物品结构体
struct Item {
    int weight;
    int value;
};

// 比较单位价值
bool compare(Item a, Item b) {
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}

// 分数背包问题
double fractionalKnapsack(int W, vector<Item>& items) {
    // 按单位价值排序
    sort(items.begin(), items.end(), compare);

    double totalValue = 0.0; // 背包中物品的总价值

    for (auto& item : items) {
        if (W >= item.weight) {
            // 如果当前物品可以完全装入
            W -= item.weight;
            totalValue += item.value;
        } else {
            // 装入部分物品
            totalValue += item.value * ((double)W / item.weight);
            break; // 背包已满
        }
    }

    return totalValue;
}

int main() {
    int W = 50; // 背包容量
    vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};

    double maxValue = fractionalKnapsack(W, items);
    cout << "背包可以装入的最大价值为: " << maxValue << endl;

    return 0;
}

📝 代码解析：

1. 将物品按单位价值降序排序。
2. 遍历物品：
   • 如果物品可以完全装入背包，则加入背包。
   • 如果不能完全装入，则加入部分物品。
3. 返回背包中的总价值。

✅ 输出示例：

背包可以装入的最大价值为: 240

---

6. 贪心算法的总结

6.1 使用贪心算法的步骤

1. 理解问题，判断是否满足贪心选择性和最优子结构。
2. 明确每一步的贪心策略。
3. 实现贪心算法，确保选择的局部最优解是合理的。
4. 验证最终解是否是全局最优解。

6.2 贪心算法的思维方式

• 每次做出局部最优选择。
• 确保当前选择不会影响整体解的最优性。
• 结合实际问题，灵活设计贪心策略。

---

7. 常见的贪心算法题型

• 选择问题：活动选择问题
• 路径问题：Dijkstra 最短路径
• 构建问题：哈夫曼编码
• 分配问题：分数背包问题

---

贪心算法虽然简单高效，但需要仔细分析问题，确保满足贪心选择性和最优子结构。在适用场景下，贪心算法无疑是一种强大的工具。