第 39 课：贪心算法

贪心算法在生活中处处可以用到，比如在购物凑单满减时，我们可以先从自己想要的商品中挑选价格高的商品加入购物车，这样可以用最少的商品达到满减的门槛。在每次选择中都做出对当下最有利的凑单选择，这便是贪心策略。

日常行程安排也可以用到贪心算法，比如一天内要去多个地方，可以优先处理耗时短、距离近的行程，这样能在有限时间内完成更多的任务。

还有书架的整理，按图书常用程度从高到低排列，方便每次最快找到所需图书。

贪心算法让我们在面对生活中的各类选择时，依据当下最优原则迅速行动，高效利用资源，提升生活效率。这不，学校举办了义卖活动，蛙蛙便用到了贪心策略，提高了他找钱的效率，让我们一起来看看吧！

39.1 策略演示

场景设定

学校最近举行了义卖活动，蛙蛙也报名参加了此项活动，准备把自己闲置的东西拿出来卖。

现在来了一位顾客买了一样东西，这件物品蛙蛙的售价是 37 元，顾客给了 100 元，现在需要蛙蛙找零 63 元。

但是蛙蛙只有一些 1 元、5 元、10 元、20 元的钞票能找给顾客，怎么找零才能使得找零的钞票数量最少呢？

案例分析

氪町博士告诉蛙蛙，可以采用贪心策略，每次选择面值最大的钞票。

首先选择面值为 20 元的钞票，63 元里最多可以选 3 个 20 元（20 × 3 = 60 元），此时剩余找零金额为 63 − 60 = 3 元。

接着，因为剩余金额小于 10 元和 5 元，无法选择这两种面值的钞票，所以选择面值为 1 元的钞票，3 元里最多可以选 3 个 1 元（1 × 3 = 3 元），此时刚好找零完毕。

总共使用的钞票数量为 3（20 元钞票数量）+ 0（10 元钞票数量）+ 0（5 元钞票数量）+ 3（1 元钞票数量）= 6 张。

通过贪心算法，蛙蛙使用 6 张钞票完成了 63 元的找零。

39.2 概念及证明

贪心算法的概念

刚刚蛙蛙制订出了合理的贪心策略，但是在编程中贪心算法是用计算机来模拟一个贪心的人做出决策的过程，你可以想象这个人十分贪婪，他每一步行动总是按某种指标选取最优的操作，而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是所有时候贪心算法都能获得最优解，所以一般使用贪心算法的时候，都要确保自己能证明其正确性，那又该怎么去证明呢？

证明方法

贪心算法有两种证明方法：反证法和归纳法。

但一般情况下，一道题只会用到其中的一种方法来证明。

反证法：如果交换方案中任意两个元素或者相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。

归纳法：先算出边界情况（例如 n = 1）的最优解 F1，然后再去证明对于每个 n，Fn+1 都可以由 Fn 推导出来。

39.3 实例讲解

例 1：过河方案

蛙蛙和他的小伙伴们一起去秋游，现在他们来到了一条小河边，需要乘坐小木船前往河对岸的景点游玩。

已知每只小木船的空间有限，最多只能搭载两个人，并且由于小木船的承重限制，乘客的总重量不能超过小木船的最大承载量。考虑到租用小木船是需要支付一定费用的，为了尽可能地节省秋游的开支，蛙蛙希望能找到一种方案，使用最少数量的小木船将所有人都顺利送到河对岸。

现在已知小木船的最大承载量、参与秋游需要过河的总人数，以及每个人的具体重量信息。请你发挥聪明才智，帮助蛙蛙计算出能够让所有人都成功过河的最少小木船数量，并将这个结果输出告知蛙蛙，以便他能更好地安排此次秋游的行程和费用预算。

【输入格式】输入两行。

第 1 行有两个整数 w 和 n，w 为一只小木船的最大承载量，n 为人数（80 ≤ w ≤ 200，1 ≤ n ≤ 300）。

第 2 行是一组数据，为每个人的重量（每个人的体重都不能大于船的承载量）。

【输出格式】输出一行，为需要的小木船的最少数量。

【输入样例 1】

85 6
5 84 85 80 84 83

【输出样例 1】

5

【输入样例 2】

100 5
50 50 90 40 60

【输出样例 2】

3

解析

为了能用最少的船帮助所有人过河，每次要尽量运送最多的人，但是比较重的人有可能每次只能自己一个人过河，再加一个人的重量就超过了最大载重。于是我们就考虑到最佳的方案如下。

1. 对所有乘客体重降序（升序也可以）排序。

2. 因为一只小木船最多只能乘坐两个人，且乘客的总重量不能超过小木船的最大承载量，所以先将升序的体重首尾（最轻和最重的）相加，如果不超过最大载重，两人坐一艘船即为最优解，那么下一组比较次轻的和次重的。

但是如果超过最大载重，则最重的那人坐一艘船，对最轻的和次重的人重复步骤 2)。

3. 最后，当次轻和次重的是同一人时，他一人坐一艘船。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
// 自定义比较函数，用于将数组元素从大到小排序
bool cmp(int a, int b)
{
    return a > b;
}
int main()
{
    int n, a[350], t = 0, w;
    cin >> w >> n; // 输入小木船的最大承载量 w 和人数 n
    int j = n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 使用自定义的比较函数，将数组 a 中的元素从大到小排序
    sort(a + 1, a + 1 + n, cmp);
    int i = 1;
    // 贪心策略
    while (i <= j)
    {
        // 如果最重的人和最轻的人的重量之和超过了船的承载量
        if (a[i] + a[j] > w)
        {
            t++; // 则最重的人单独坐一条船，船的数量加 1
            i++; // 继续考虑下一个最重的人
        }
        else if (a[i] + a[j] <= w) // 如果两人重量之和不超过船的承载量
        {
            t++; // 则他们可以坐同一条船，船的数量加 1
            i++;
            j--; // 继续考虑下一个最重的人和下一个最轻的人
        }
    }
    cout << t; // 输出需要的小木船的最少数量
    return 0;
}

例 2：救援物资

蛙蛙爸爸开着卡车准备给灾区送一些救援物资，他的卡车最大载重量为 m 公斤，同时他购买了 n 种食品，有食盐、白糖、大米等。

已知第 i 种食品的重量为 Wi 公斤，其商品价值为 Vi 元/公斤，为了让装入卡车中的所有食品总价值最大，蛙蛙准备通过编程帮助爸爸确定一个装货方案。

【输入格式】输入 n + 1 行。

第 1 行为卡车最大载重量 m 公斤和 n 种食品。

接下来 n 行，每行表示第 i 种食品的重量 Wi 和价值 Vi。

【输出格式】输出一行，为装入卡车的食品的总价值，结果保留两位小数。

【输入样例】

10 3
3 4
4 5
2 6

【输出样例】

44.00

解析

为了使装入卡车的食品价值最大，每次选取的必然是价值最大的食品。

1. 首先我们可以将每种食品的价值按照从大到小的顺序排列，然后每次选取价值大的食品。

2. 在装载食品之前需要判断重量是否超过卡车最大载重量，如果超过了，装至最大载重量并结束，否则将食品全部装入。

3. 最后将卡车最大载重量减去已装入的食品重量，重复以上步骤直至结束。

参考代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct s
{
    double w, v; // 重量，价值
} a[105];
// 按照食品的价值从大到小排序
bool cmp(s p, s q)
{
    return p.v > q.v;
}
int main()
{
    int m, n;
    cin >> m >> n;
    // 循环读取每种食品的重量和价值
    for (int i = 1; i <= n; i++)
        cin >> a[i].w >> a[i].v;
    // 使用 sort 函数对结构体数组 a 进行排序
    sort(a + 1, a + n + 1, cmp);
    double sum = 0;
    for (int i = 1; i <= n; i++)
    {
        // 判断当前食品的重量是否小于或等于卡车的剩余载重量
        if (a[i].w <= m)
        {
            // 如果小于或等于，将该食品全部装入卡车，将总价值累加到 sum 中
            sum += a[i].w * a[i].v;
            // 卡车的剩余载重量减去该食品的重量
            m -= a[i].w;
        }
        else
        {
            // 如果当前食品的重量大于卡车的剩余载重量，则只能装入部分该食品
            sum += m * a[i].v;
            // 此时卡车已装满，结束装货过程，跳出循环
            break;
        }
    }
    // 输出总价值，保留两位小数
    printf("%.2f\n", sum);
    return 0;
}

例 3：会场安排

在公司里工作会经常涉及沟通与决策，因此每天都会有很多会议需要开展。

然而，蛙蛙妈妈的公司仅配备了一个设施完备的大会议室。由于大会议室资源有限，一旦某场会议被安排在特定时间段，例如 8 点至 9 点，那么该时间段内便无法再安排其他任何会议。

蛙蛙的妈妈兼任公司的排班人员，手头掌握着一张详细的会议安排计划时间表。表中罗列了众多会议的预计开始时间和结束时间等关键信息。

但如何更好地利用这唯一的大会议室资源，成为蛙蛙妈妈工作中的一大挑战。她期望在满足公司会议需求的基础上，尽可能地在大会议室安排更多的会议场次。她还希望在保证会议数量的同时，让大会议室占用更少的时间，从而为每次会议之间留出充裕的时间，以便工作人员对会议室进行清理、设备调试等准备工作，确保后续会议能够顺利进行。

现在，蛙蛙听说了此事，决定帮妈妈解决这个复杂而重要的会议室安排问题，为妈妈的公司贡献出自己的一份力量。

【输入格式】输入 n + 1 行。

第 1 行输入一个正整数 n，表示一共有 n 场会议（1 ≤ n ≤ 100）。

之后的每行分别记录这 n 场会议的开始和结束时间（整点，时间在 0 和 24 之间）。

【输出格式】输出两行，第 1 行输出安排好之后的第一场会议的开始和结束时间，第 2 行输出这间大会议室最多安排几场会议。

【输入样例】

4
8 9
10 12

【输出样例】

8 9
2

注：原书样例输入 n 为 4，但仅列出 2 场会议的数据，疑为原书排版遗漏，此处按原文呈现。

解析

解决这道题的思路是，我们先安排一场会议，再在安排了这场会议的前提下，在剩下的时间里尽可能多地安排其他会议。

1. 我们不妨先安排整个会议室里的第一场会议，然后再在这场会议结束之后剩余的时间里安排尽可能多的会议。

2. 在安排完一场会议之后，要使得剩下的时间尽可能多，这样就可以安排更多的会议。所以我们每一次首先安排的会议是结束时间最早的那一场会议，因为结束时间最早的那场会议被先安排的话剩余时间是最多的。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
// 定义结构体 s，用于存储每场会议的开始时间和结束时间
struct s
{
    int st, ed; // st 表示会议开始时间，ed 表示会议结束时间
} a[110];
bool cmp(s b, s c)
{
    if (b.ed != c.ed)
        return b.ed < c.ed; // 优先按照结束时间从小到大排序
    return b.st > c.st;     // 若结束时间相同，则按照开始时间从大到小排序
}
int main()
{
    int n, t = 0, j = 0;
    cin >> n;
    // 读取每场会议的开始时间和结束时间
    for (int i = 1; i <= n; i++)
        cin >> a[i].st >> a[i].ed;
    sort(a + 1, a + 1 + n, cmp); // 按照自定义规则排序
    // 遍历排序后的结构体数组 a
    for (int i = 1; i <= n; i++)
    {
        // 判断当前会议的开始时间是否大于或等于上一场已安排会议的结束时间
        if (a[i].st >= j) // 如果满足条件，则可以安排该会议
        {
            // 更新上一场已安排会议的结束时间为当前会议的结束时间
            j = a[i].ed;
            // 已安排会议的数量加 1
            t++;
        }
    }
    // 输出安排好之后的第一场会议的开始和结束时间
    cout << a[1].st << " " << a[1].ed << endl;
    // 输出这间大会议室最多安排的会议数量
    cout << t;
    return 0;
}