Skip to content
酷学小栈

C++贪心算法

📚 C++ 中贪心算法详解 1. 贪心算法的定义 贪心算法 (Greedy Algorithm)是一种在每一步选择中都采取当前状态下 局部最优 的选择,以期最终达到 全局最优解 的算法。 1.1 核心思想 局部最优选择 :在问题的每一步中,都选择当前看起来最优或最有利的选项。 全局最优目标…

On this page
  1. 1. 贪心算法的定义
  2. 1.1 核心思想
  3. 1.2 贪心算法的适用条件
  4. 1.3 贪心算法与其他算法的区别
  5. 2. 贪心算法的基本步骤
  6. 3. 贪心算法的优缺点
  7. ✅ 优点:
  8. ❌ 缺点:
  9. 4. 贪心算法的经典应用场景
  10. 5. 贪心算法的经典例题
  11. 示例:分数背包问题(Fractional Knapsack Problem)
  12. C++ 实现
  13. 6. 贪心算法的总结
  14. 6.1 使用贪心算法的步骤
  15. 6.2 贪心算法的思维方式
  16. 7. 常见的贪心算法题型

📚 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 最短路径
  • 构建问题:哈夫曼编码
  • 分配问题:分数背包问题

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