#贪心算法

从名字就可看出，贪心算法是一个追求最好结果的一个过程。

当我们面临一个需要做出一系列决策的问题时，贪心算法是一种可以帮助到我们去快速找到近似最优解的方法。

#贪心算法基本思想

贪心算法的核心思想是 贪心 ：即每一步都采取当前状态下最优的决策，从而期望最终得到全局最优解。这种选择可能不是全局最优的，但它在局部上一定是最优的。通过这种重复的决策过程，最终可以得到一个近似最优的解。

举个例子，假设你要自驾去一个距离很远的地方，在路途中每隔一段距离就有一个加油站，你需要决定在哪些加油站加油才能保证到达终点。如果采用贪心算法，我们希望整个中途中加油的次数最少，那每次我们就尽可能选择距离最远（但要保证车能开到）的加油站去加油，这样每次加油就是最优的（局部最优），最终也能得到一个比较不错的加油策略（近似全局最优）。

在编程中，贪心算法可以应用去解决很多问题，比如最小生成树问题、最短路径问题、背包问题等。

#贪心算法求解的步骤

使用贪心算法解决问题的三个步骤：

1. 定义问题空间。理解问题，我们是需要解决一个什么样的问题。
2. 确定贪心策略。每一步采取什么样的策略才是最优的。
3. 通过贪心策略去求解问题。

假设我们去买衣服，一件衣服价格 367 元，而我们手上有面额为 1 元、2元、5元、10元、20元、50元、100元的钞票若干张，怎样支付这笔钱，才能使得给出的钞票张数最少呢？

看起来并不复杂，要使得给出的钞票张数最少，我们只需要从面额最大的钞票开始给就行了。

将钞票面额从大到小先排个序：

口算一下就可以得到：

• 需要 3 张 100 元的，这里就有 300 元了
• 再需要 1 张 50 元的，这里就共有 350 元（300 + 50）
• 再需要 1 张 10 元的，这里就共有 360 元（350 + 10）
• 再需要 1 张 5 元的，这里就共有 365 元（360 + 5）
• 再需要 1 张 2 元的，这里就共有 367（365 + 2）

这样计算出的所需要的钞票数量最少。

如果用代码来实现，可写出下面的代码：

#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  
  int a, b, c, d, e, f, g;
  
  a = n / 100; n %= 100;
  b = n / 50; n %= 50;
  c = n / 20; n %= 20;
  d = n / 10; n %= 10;
  e = n / 5; n %= 5;
  f = n / 2; n %= 2;
  g = n;
  
  cout << a << " 张 100 元" << endl;
  cout << b << " 张 50 元" << endl;
  cout << c << " 张 20 元" << endl;
  cout << d << " 张 10 元" << endl;
  cout << e << " 张 5 元" << endl;
  cout << f << " 张 2 元" << endl;
  cout << g << " 张 1 元" << endl;
  cout << "共使用了 " << a + b + c + d + e + f + g << " 张钞票！" << endl;
  return 0;
}

输入数据

输出数据

#练习：最少所用钞票张数

#问题描述

将上面的问题再稍微变得更通用一点，钞票的面额以及衣服的价格均由用户去输入，仍然是找出如何给，才能使得所使用的钞票数量最少（假设每种面额的钞票数量无限制）。

这就是一个典型的可以使用贪心算法去解决的问题。仍然是三个步骤：

1. 确定问题空间。通过已知面额的钞票去凑出所要给的金额，要求所使用的钞票张数最少。
2. 确定贪心策略。每一步都是从面额最大的钞票去尝试。
3. 通过贪心策略去求解问题。先将面额从大到小排序，然后每次去看需要使用面额最大的钞票几张？然后是要使用的第二大面额的钞票几张？依次下去，直到凑出给出的金额。

#输入描述

共两行，第一行两个整数 $n$ 和 $m$，分别是钞票面额的种数以及购买时需要给的金额；第二行是具体的 $n$ 种钞票面额分别是多少。

#输出描述

输出为一行，代表最少所使用的钞票的数量；如果根据现有的面额无法直接凑出所需要的金额，则输出 -1 。

#输入输出样例

#输入 1

#输出 1

#代码实现

• 3zjez4szy - C++ - OneCompiler

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

const int N = 50;
int q[N];

bool cmp(int x, int y) {
  return x > y;
}

int main() {
  int n, m, rlt = 0;
  cin >> n >> m;
  
  for (int i = 0; i < n; i++) cin >> q[i];
  
  sort(q, q + n, cmp);
  
  for (int i = 0; i < n; i++) {
    if (m >= q[i]) {
      int cnt = m / q[i];
      rlt = rlt + cnt;
      m = m % q[i];
    }
  }
  
  if (m == 0) cout << rlt << endl;
  else cout << -1 << endl;
  
  return 0;
}

#练习：排队接水问题 V1

#题目描述

有 $n$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$，请编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。

#输入格式

第一行为一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的等待时间 $T_i$。

#输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

#输入 #1

#输出 #1

#说明提示

• $n \leq 1000,t_i \leq 10^6$，不保证 $t_i$ 不重复。

• 当 $t_i$ 重复时，按照输入顺序即可（sort 是可以的）

#代码实现

• 代码：3z5shxcff - C++ - OneCompiler

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

const int N = 1010;

struct Person {
  int t, p;
} persons[N];

bool cmp(Person a, Person b) {
  return a.t < b.t;
}

int main() {
  int n;
  cin >> n;
  
  for (int i = 1; i <= n; i++) {
    cin >> persons[i].t; // 记录这个人的接水时间
    persons[i].p = i; // 记录原始位置
  }
  
  sort(persons + 1, persons + n + 1, cmp);
  
  for (int i = 1; i <= n; i++) {
    cout << persons[i].p << " ";
  }
  
  cout << endl;
  
  // 统计时间
  double t = 0;
   /**
   * i < n 是因为当 i 为 n 时实际计算的是
   * 第 n + 1 个人的总等待时间
  **/
  for (int i = 1; i < n; i++) {
    persons[i].t =  persons[i].t + persons[i - 1].t;;
    t += persons[i].t;
  }
  
  printf("%.2lf", t / n);
  
  return 0;
}

#练习：排队打水问题 V2

#题目描述

有 $n$ 个人排队到 $r$ 个水龙头去打水，他们装满水桶的时间 $t_1,t_2,t_3...t_n$ 为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的总时间最少？

每个人打水的时间 = 排队的时间 + 实际打水的时间，本题假设一个人打好水，排在他后面的人接着打水的这个切换过程不消耗时间。

比如，有 2 个人 $A$ 和 $B$ ，他们打水的时间分别是 3 和 2 ，只有 1 个水龙头，这时，如果 $A$ 先打水，$B$ 后打水，那么 $A$ 和 $B$ 打水的时间分别为 3 、3+2（ $B$ 排队 3 分钟）。

因此，所有人打水的总时间就是每个人的打水时间及每个人的排队时间的总和。

#输入

第 1 行，两个整数 $n$ ( $1 \le n \le 500$) 和 $r$ ( $1 \le r \le 100$ )。

第 2 行，$n$ 个正整数 $t_1,t_2,t_3...t_n$ ，( $1 \le t_i \le 1000$ )表示每个人装满水桶的时间。

#输出

1 行，一个正整数，表示他们花费的最少总时间。

#输入输出样例

#输入数据

#输出数据

#题目解析

首先，容易知道，要得所有人打水的总时间最少，只需要每个人打水的总时间最少即可，这就是我们确定的贪心策略。

每个人打水的总时间 = 这个人打水的时间 + 这个人需要等待的时间，而每个人打水的时间是固定的，只需要他的等待时间最少就行了。

因此我们只需要将所有人依据他们打水的时间由小到大排序，时间越少的排在前面，后面的人所需等待的时间也就越少。

如果有 $r$ 个水龙头，前 $r$ 个人刚好每个人排一个水龙头，因此是不需要等待时间的，从 $r+1$ 个人开始就需要等待了，第 $r+1$ 个人刚好排在 1 号水龙头接水， 第 $r+2$ 个人刚好排在 2 号水龙头接水，依此类推，第 $i$ 个人刚好排在 $i-r$ 号水龙头接水。

有了上面的分析，代码也就不难写出了。

#代码实现

• 3zhqq2867 - C++ - OneCompiler

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

const int N = 505;
int q[N];

int main() {
    int n, r, t = 0;
    cin >> n >> r;
    
    for (int i = 1; i <= n; i++) cin >> q[i];
 
    sort(q + 1, q + n + 1);
    
    for (int i = 1; i <= n; i++) {
      // 第 i 个人花费的时间 = 打水时间 + 等待时间
      if ( i > r) q[i] = q[i] + q[i - r]; 
      t = t + q[i];
    }
    
    cout << t << endl;
    return 0;
}

#练习：导弹拦截问题

#题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

假设某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入 $n$ 个导弹依次飞来的高度（给出的高度数据是不大于 30000 的正整数），计算如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

比如：有 8 颗导弹，飞来的高度分别为

389 207 175 300 299 170 158 165

那么需要 2 个系统来拦截，他们能够拦截的导弹最优解分别是：

系统 1 ：拦截 389 207 175 170 158

系统 2 ：拦截 300 299 165

#输入

两行，第一行表示飞来导弹的数量 $n$（$n \le 1000$ ）；

第二行表示 $n$ 颗依次飞来的导弹高度；

#输出

要拦截所有导弹最小配备的系统数 $k$ 。

#输入输出样例

输入数据

输出数据

#题目解析

（待补充）

#代码实现

• 3zhqubtfn - C++ - OneCompiler

#include <iostream>
using namespace std;

const int N = 1010;
int q[N];

int main() {
  int n, k = 0;
  cin >> n;
  
  for (int i = 0; i < n; i++) {
    int m;
    cin >> m; 
    
    int f = -1;
    for (int j = 0; j < k; j++) {
      if (q[j] >= m) {
        f = j;
      }
    }
    
    if (f == -1) {
      q[k++] = m; // 如果系统内找不到拦截高度，新建系统
    } else {
      q[f] = m; // 修正系统内的导弹拦截高度
    }
  }
    
  cout << k << endl;
  return 0;
}

#小结

贪心算法是一种常用的算法思想，常用于解决优化问题。它通过每一步选择当前情况下的最优解，从而希望达到全局最优解。贪心算法的优点是简单高效，通常时间复杂度较低。但它的缺点是不能保证得到全局最优解，并不是所有问题都适合使用贪心算法，有些问题可能需要使用其他算法来解决。