前言

贪心算法是必须掌握的一种基础算法，在一些比较出名的竞赛acm、蓝桥杯，并且在一些公司面试题中都可能会出现，而且作为简单题我们必须要拿下，所以我们要引起重视，下面让我们来深入了解贪心。

一、什么是贪心算法

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。它通常用于解决优化问题，如寻找最短路径、最小生成树、任务调度等。贪心算法并不总是能找到全局最优解，但在某些特定问题中，贪心策略可以确保找到最优解或近似最优解。

二、算法原理

贪心算法的核心思想是，在每一步选择中都做出局部最优的决策，即在当前状态下选择最好或最优的解，然后基于这个选择继续构建问题的解，直到得到完整的解或无法再做出选择。

三、贪心算法的基本步骤

1.问题描述：明确问题的目标，即需要优化的目标函数。

2.选择策略：确定每一步选择中的最优标准（贪心选择）。

3.构造解：通过逐步构建解的方式，每一步都根据贪心选择策略选择当前最优解。

4.证明：证明贪心选择能导致全局最优解（如果可能）。如果不能证明，则可能需要通过其他方法验证解的有效性。

四、贪心算法的特点

1.局部最优：每一步都选择当前状态下的最优解。
2.简单高效：通常贪心算法实现简单，运行效率高。
3.不一定全局最优：在某些情况下，贪心算法可能无法找到全局最优解。

五、优缺点分析

优点：
时间复杂度通常较低，具有较高的效率。实现简单，容易理解和实现。

缺点：
不能保证得到全局最优解，有时可能因局部选择导致全局次优解。
对于某些需要回溯或组合的情况，贪心算法可能不适用。

六、适用条件

贪心算法适用于具有贪心选择性质和最优子结构性质的问题。贪心选择性质是指，可以通过局部最优解一步步获得全局最优解。最优子结构性质是指，问题可以通过子问题的最优解构建得到全局最优解。

七、经典应用

最小生成树：如Prim算法和Kruskal算法，通过逐步添加权重最小的边来构建最小生成树。

最短路径：如Dijkstra算法，通过逐步选择当前未访问顶点中距离源点最近的顶点来构建最短路径。

背包问题：在物品可以分割的情况下，通过选择单位重量价值最高的物品来最大化背包的价值。

活动选择问题：在一组互不相容的活动中，选择不冲突且结束时间最早的活动来最大化活动数量。

哈夫曼编码：通过逐步合并频率最低的字符合并来构建最优的前缀编码。

七、实例分析

以背包问题为例，假设有一个背包，背包容量是M，有n个物品，每个物品有一个重量和价值。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。贪心算法的一种策略是选择单位重量价值最高的物品直到背包装满。然而，这种策略并不总是能得到全局最优解，因为可能存在一些物品组合在一起的价值更高。但在物品可以分割的情况下，这种策略是有效的，因为可以按需分割物品来最大化价值。

八、经典例题

1.翻硬币

帅哥们这个蓝色字体可以点进去看原题

代码题解

#include <iostream>
#include<string>
using namespace std;
int main()
{
  
  // 请在此输入您的代码
  string s,t;
  cin>>s;
  cin>>t;
  int n=s.size();
  int cnt=0;
  for(int i=0;i<n;i++){
    if(s[i]!=t[i]){//翻转两次所以，如果初始状态与目标状态不一样就翻转
      s[i]=(s[i]=='*'?'o':'*');
      s[i+1]=(s[i+1]=='*'?'o':'*');
      cnt++;
    }
  }
  cout<<cnt<<endl;
  return 0;
}

2.一键三连

帅哥们这个蓝色字体可以点进去看原题

代码题解

#include <iostream>
#include<algorithm>
using namespace std;

int a[100001];

int main()
{
  // 请在此输入您的代码
  int n;
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,a+n);//给数组进行排序
  int l=1,r=1;
  while(r<n){//去重处理
    if(a[r]!=a[l-1])a[l++]=a[r];//把没有重复的数重新放到a数组里
    r++;
  }
  int res=0;
  for(int i=0;i<l;i++){
    int x=a[i];
    if(x+1==a[i+1]&&a[i+2]==x+2)res++;
  }
  cout<<res<<endl;
  return 0;
}

3.分开元音字母

帅哥们这个蓝色字体可以点进去看原题

#include <iostream>
#include<string>
using namespace std;

bool isYy(char a){
    return a=='a'||a=='e'||a=='i'||a=='o'||a=='u';
}

string ret;
string s;

int main()
{
    cin>>s;
    ret="(";
    int n=s.size();
    int flag=0,cnt=0;
    for(int i=0;i<n;i++){
        if(isYy(s[i])){
            cnt++;
            flag=1;
            if(cnt>1){
                ret+=")(";
                cnt=1;
            }
            
        }
        ret+=s[i];
    }
    ret+=")";
    if(!flag)ret=s;//从来没出现过元音字母
    cout<<ret<<endl;

  return 0;
}

九、结语

学习算法是一个很艰难，漫长的过程，我们要克服一切困难，学习算法本就是由易到难，不会的地方就问，我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节，加油，我相信你一定能行。

关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家。