贪心算法

贪心的定义

-贪心搜索算法是一种在每一步选择中都采取当前状态下最优的选择，以达到整体的局部最优解。它不保证最终结果是最佳的全局解，但在某些情况下提供了一种快速且实用的解决方案。贪心算法在解决最短路径问题等方面应用广泛，尤其是在图和树的搜索中表现出高效的性能。

比如，你面前有一堆不同面额的硬币（比如 1 元、5 角、1 角），你需要用最少数量的硬币凑出 1.8 元。一个很自然的想法是：每次都先拿面额最大的硬币。先拿 1 元，剩下 0.8 元；再拿 5 角，剩下 0.3 元；最后拿三个 1 角。整个过程，我们在每一步都做出了 当前看来最好的选择，这就是贪心算法的核心思想。

贪心算法就像是一个目光短浅但决策果断的人：

·每一步选择：在当前状态下做出看起来最优的选择

·不考虑全局：不考虑这个选择对未来的影响

·期望结果：希望局部最优选择能导致全局最优解

现实中的案例：

·找零钱：总是先用最大面额的硬币

·爬山：总是朝最陡峭的方向前进

·购物：总是买当前最优惠的商品

·路线选择：总是选择当前最短的路

贪心算法的特点

·贪心选择性质：每一步的最优解，都可以由之前各步的局部最优解推导出来。后面的选择不会影响之前的选择。

·最优子结构：一个问题的最优解包含其子问题的最优解。这是动态规划也具有的性质，但贪心算法在每一步都”贪心地”选择子问题的最优解。 屏幕截图 2026-01-28 115556.png

与动态规划的区别 屏幕截图 2026-01-28 115903.png

贪心算法的基本框架

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     //1、初始化：包括排序、创建结果容器等
  6.     //2、遍历所有可选项，通常需要先按某种规则排序
  8.     //3、贪心选择：如果当前选择满足条件，就采纳它
  10.     //4、返回最终构造的解
  11.     return 0;
  12. }

经典问题与代码示例

1、平均分配问题

【问题描述】 有 N 堆苹果，编号分别为 1，2，…, N。每堆上有若干个，但苹果总数必为 N 的倍数。可以在任一堆上取若干个苹果，然后移动。移苹果规则为：在编号为 1 堆上取的苹果，只能移到编号为 2 的堆上；在编号为 N 的堆上取的苹果，只能移到编号为 N-1 的堆上；其他堆上取的苹果，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上苹果数都一样多。

输入：N（N 堆苹果，1 <= N <= 100）A1 A2 … An （N堆苹果，每堆苹果初始数，1<= Ai<=10000） 输出：所有堆均达到相等时的最少移动次数。

代码如下：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int p[1005];
  4. int main(){
  5.     int n,i;
  6.     cin>>n;
  7.     int f=0, c=0;
  8.     for( i=0;i<n;i++){
  9.         cin>>p[i];
  10.         f+=p[i];
  11.     }
  12.     f/=n;
  13.     for(i=0;i<n-1;i++){
  14.         if(p[i] != f){
  15.             p[i+1]=p[i+1]-(f-p[i]);
  16.             c++;
  17.         }
  18.     }
  19.     cout<< c;
  20.     return 0;
  21. }

2、找零钱

【问题描述】 悟空和八戒在集市买苹果，现需要找给客户N元零钱。假设有数目不限，面值为20,10,5,1的硬币。如何使得找出的硬币数量最少？

输入：一个正整数n，表示需要找的零钱数目。（0<n<100)

输出：找出的最少零钱数目。

代码如下：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     int n;
  5.     cin>>n;
  6.     int count = 0;
  7.     int coins[] = {20,10,5,1};
  8.     for(int i = 0;i < 4 ;i++){
  9.         count += n/coins[i];
  10.         n = n % coins[i];
  11.     }
  12.     cout<<count;
  13.     return 0;
  14. }

3、活动选择

题目描述

学校在最近几天有n个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。

现在给出n个活动使用礼堂的起始时间begin_i和结束时间end_i(begin_i < end_i),请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。

代码如下：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct JGT{
  4.     int s;
  5.     int t;
  6. }a[1005];
  7. int n;
  8. bool cmp(JGT x,JGT y){
  9.     return x.t<y.t;
  10. }
  11. int cnt = 0;
  12. int main(){
  13.     cin>>n;
  14.     for(int i=0;i<n;i++){
  15.         cin>>a[i].s>>a[i].t;
  16.     }
  17.     sort(a+1,a+1+n,cmp);
  18.     int m = 0;
  19.     for(int i=1;i<=n;i++){
  20.         if(a[i].s>=m){
  21.             cnt++;
  22.             m=a[i].t;
  23.         }
  24.     }
  25.     cout<<cnt;
  26.     return 0;
  27. }

4、额外的报酬

题目描述

假设本月新收若干个不同订单，其难易程度为一级、二级、三级…同样，能够完成不同难度订单的工人也被分为若干星级，并且x星级的工人能够完成x级别以下的所有任务。

现有m个订单，n个空闲工人，请问能否完成所有订单呢？如果可以，最少的花费是多少呢？

注：每个工人当月只能完成一件任务。

输入： 第一行两个整数m和n，分别表示订单量和工人量。 （1<=n,m<=20000）

第二行m个整数，表示每个订单的难易级别；

第三行n个整数，表示每个工人的星级。

输出：如果可以完成：第一行输出最小花费，接下来m行每行两个整数，分别表示订单级别与相应的工人级别（用空格隔开）。否则，直接输出“Failed”。

5、八戒的礼物

题目描述

八戒购买了若干件礼物，想要以“价值相对均衡”为前提，将礼物进行分组，并且保证每组礼物件数不超过两件，同时保证每组的礼物价值总和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有礼物，八戒要使分组数最少，你知道他是如何完成的吗？

输入：第一行两个整数max和n，分别表示每组礼物的价值上限、礼物总件数；（1<=n<=30000，10<=max<=1000）

第二行有n的整数x，分别表示n件礼物的价值。（5<=x<=max）

输出：一个整数，表示最少的分组数目。

代码如下：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int Max =  100000;
  4. int main(){
  5.     int max,n;
  6.     cin>>max>>n;
  7.     int p[Max];
  8.     for(int i=0;i<n;i++){
  9.         cin>>p[i];
  10.     }
  11.     sort(p,p+n);
  12.     int r = n - 1, l = 0;
  13.     int count = 0;
  14.     while(l <= r){
  15.         if(p[l]+p[r] <= max){
  16.             l++;
  17.         }
  18.         r--;
  19.         count++;
  20.     }
  21.     cout<<count<<endl;
  22.     return 0;
  23. }