讲义

贪心算法

2024/9/1

# 基本概念

贪心算法（Greedy Algorithm）在解决问题时，总是做出在当前看来是最优的选择。它只考虑局部最优解，并不从整体最优的角度考虑。因此，贪心算法的关键在于选择合适的贪心策略，该策略必须具备无后效性，即某个状态以后的过程不会影响之前的状态，只与当前状态相关。

注意：贪心算法并不适用于所有问题，选择的策略必须仔细分析是否满足无后效性，否则可能无法得到整体最优解。

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望能够得到问题的全局最优解的算法。贪心算法的核心思想是局部最优策略的累积能够带来全局最优。

# 贪心算法与动态规划的对比

  • 贪心算法：每一步都选择局部最优解，不能回溯，一般不能保证全局最优解。
  • 动态规划：适用于最优子结构和重叠子问题，通过递归或迭代构建全局最优解。

# 应用场景

贪心算法通常应用于以下问题：

  • 找零问题
  • 最短路径问题（如 Dijkstra 算法）
  • 最小生成树问题（如 Kruskal 和 Prim 算法）

# 贪心算法的实现步骤

  1. 选择贪心策略：找出能够带来局部最优解的策略。
  2. 验证贪心策略的正确性：通过数学证明或反例验证，确认贪心策略能带来全局最优解。
  3. 实现贪心算法：根据选择的策略进行编码实现。

# 贪心算法的经典例题

  1. 零钱兑换问题

问题描述：给定几种不同面值的硬币和一个总金额，要求找出用这些硬币凑成总金额所需的最少硬币数。

贪心策略：每次选择面值最大的硬币。

  1. 活动选择问题

问题描述：给定一系列活动，每个活动都有开始和结束时间，选择尽可能多的活动参加，但不能有重叠的活动。

贪心策略：每次选择结束时间最早且不与已选择的活动冲突的活动。

  1. 霍夫曼编码

问题描述：霍夫曼编码是一种常用于数据压缩的编码方式，其核心思想是用较短的编码表示频率较高的字符，较长的编码表示频率较低的字符。

贪心策略：每次选择频率最低的两个节点合并，直到只剩下一个节点。

# 例题代码实现及讲解

  1. 零钱兑换问题
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minCoins(vector<int>& coins, int amount) {
    sort(coins.rbegin(), coins.rend()); // 将硬币按面值从大到小排序
    int count = 0;
    
    for (int coin : coins) {
        if (amount >= coin) {
            count += amount / coin; // 使用尽可能多的大面值硬币
            amount %= coin; // 更新剩余金额
        }
    }
    
    return amount == 0 ? count : -1; // 如果剩余金额为 0，则返回硬币数，否则返回 -1 表示无法凑出
}

int main() {
    vector<int> coins = {1, 2, 5, 10, 20, 50, 100};
    int amount = 93;
    
    int result = minCoins(coins, amount);
    if (result != -1) {
        cout << "最少需要 " << result << " 个硬币。" << endl;
    } else {
        cout << "无法凑出指定金额。" << endl;
    }
    
    return 0;
}

  • 代码讲解

    • sort(coins.rbegin(), coins.rend());：将硬币按面值从大到小排序，这样可以首先使用面值最大的硬币。
    • count += amount / coin;：计算当前面值硬币可以使用的数量，并累计到总硬币数。
    • amount %= coin;：更新剩余需要凑的金额。

  • 算法复杂度分析

    • 时间复杂度：O(n log n)，n 是硬币的种类数，因为有排序操作。
    • 空间复杂度：O(1)，只需要常数空间。

# 贪心算法的局限性

  • 贪心算法不适用的场景

贪心算法不适用于所有问题，尤其是当局部最优解无法组合成全局最优解时。

  • 如何识别贪心算法是否适用

通常需要通过数学证明或举反例来验证贪心算法在特定问题中的适用性。

点击查看适用反例示例
  • 例子：背包问题 (Knapsack Problem)

问题描述： 假设有一个背包，最大承重量为 W，并且有 n 个物品，每个物品有一个重量 w[i] 和一个价值 v[i]。要求在不超过背包最大承重量的前提下，选择一部分物品，使得这些物品的总价值最大化。

贪心策略： 一种常见的贪心策略是按照物品的 单位价值（价值/重量） 从大到小排序，然后尽量选择单位价值最高的物品，直到背包装满为止。

反例验证： 假设有以下三个物品：

  • 物品 1：重量 = 10，价值 = 60，单位价值 = 6
  • 物品 2：重量 = 20，价值 = 100，单位价值 = 5
  • 物品 3：重量 = 30，价值 = 120，单位价值 = 4

背包的最大承重量为 W = 50。

根据贪心策略，我们首先选择单位价值最高的物品 1（单位价值为 6），然后选择单位价值第二高的物品 2（单位价值为 5），此时背包的总重量为 30，剩余 20 的重量容量。因此，最终背包中选择的物品是物品 1 和物品 2，总价值为 60 + 100 = 160。

实际最优解： 如果我们选择物品 2 和物品 3（总重量为 20 + 30 = 50），那么总价值为 100 + 120 = 220。

可以看出，虽然贪心策略选择了局部最优的物品，但它并没有得到全局最优解。这个反例表明，贪心算法并不适用于解决背包问题。背包问题的最优解通常需要使用动态规划或其他优化算法来求解。

结论： 通过这个反例，我们验证了贪心算法在背包问题中是不适用的，原因是局部最优选择并不能保证全局最优解。

# 练习例题

  1. 排队打水问题

问题描述： 有 n 个人排队去 r 个水龙头打水，他们装满水桶的时间为 t1, t2, ..., tn（时间为整数且各不相同）。如何安排他们的打水顺序使得花费的总时间最少？

输入样例：

4 2
2 6 4 5

输出样例：

23

算法分析： 由于排队时越靠前的计算次数越多，因此越小的排在越前面总时间最少。算法步骤为：

  1. 将输入的时间按从小到大排序。
  2. 将排序后的时间按顺序依次放入每个水龙头的队列中。
  3. 统计并输出结果。

参考程序：

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

int main() {
    int n, r;
    cin >> n >> r;  // 读取人数和水龙头数量

    int times[n], s[r];
    memset(s, 0, sizeof(s));  // 初始化每个水龙头的等待时间为0

    for (int i = 0; i < n; i++) {
        cin >> times[i];  // 读取每个人装水所需的时间
    }

    sort(times, times + n);  // 对装水时间进行从小到大排序

    int minx = 0, j = 0;
    for (int i = 0; i < n; i++) {
        s[j] += times[i];  // 将时间依次加到每个水龙头的队列中
        minx += s[j];  // 累加总时间
        j = (j + 1) % r;  // 按顺序分配水龙头
    }

    cout << minx << endl;  // 输出总时间
    return 0;
}
  1. 均分纸牌问题

问题描述： 有 n 堆纸牌，每堆上有若干张纸牌，但总纸牌数必为 n 的倍数。可以在任一堆上取若干张纸牌，并移动到相邻的堆上。找出一种移动方法，使得最少的移动次数使每堆纸牌数量相等。

输入样例：

4
9 8 17 6

输出样例：

3

算法分析： 将每堆纸牌数减去平均值后，将问题转化为移动正数纸牌加到负数纸牌中，使所有堆纸牌数变为 0，移动次数即为步数。

参考程序：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;  // 读取纸牌堆数

    int a[n], ave = 0, step = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];  // 读取每堆纸牌数
        ave += a[i];  // 计算总张数
    }

    ave /= n;  // 计算平均张数
    for (int i = 0; i < n; i++) {
        a[i] -= ave;  // 每堆纸牌数减去平均数
    }

    for (int i = 0; i < n - 1; i++) {
        if (a[i] != 0) {
            a[i + 1] += a[i];  // 将第i堆纸牌移到第i+1堆
            step++;  // 移动次数加1
        }
    }

    cout << step << endl;  // 输出最少移动次数
    return 0;
}
  1. 删数问题

问题描述： 输入一个高精度正整数 n，去掉其中任意 s 个数字后，剩下的数字按原顺序组成一个新的正整数，输出这个最小的正整数。

输入样例：

175438 4

输出样例：

13

算法分析： 采用贪心策略，从高位到低位搜索，删除第一个递减区间的首字符，重复此过程 s 次，剩下的数字即为最小解。

参考程序：

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

int main() {
    char n[241];
    int s;
    cin >> n >> s;  // 读取数字和要删除的位数
    int len = strlen(n);  // 获取数字长度

    for (int i = 0; i < s; i++) {  // 删除s次
        int j;
        for (j = 0; j < len - 1; j++) {
            if (n[j] > n[j + 1]) {  // 找到第一个递减区间的首字符
                break;
            }
        }
        for (int k = j; k < len - 1; k++) {
            n[k] = n[k + 1];  // 删除字符并左移
        }
        len--;  // 更新长度
    }

    bool flag = false;
    for (int i = 0; i < len; i++) {
        if (n[i] != '0' || flag) {
            cout << n[i];  // 删除无效的0并输出结果
            flag = true;
        }
    }
    if (!flag) cout << "0";  // 如果全是0，输出0

    cout << endl;
    return 0;
}

# 真题练习

(csp-j 2021 15)有四个人要从A点坐一条船过河到B点，船一开始在A点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为1，2，4，8，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（ ）时间可以让四个人过河到B点（包括从B点把船开回A点的时间）。

  • A.14
  • B.15
  • C.16
  • D.17
点击查看解析

这道题目涉及到经典的“渡河问题”或“过桥问题”，通常用的是贪心算法来解决。贪心算法通过选择局部最优解来得到全局最优解，适用于此类问题。

四个人的过河时间分别为：1分钟、2分钟、4分钟和8分钟。由于船一次最多只能坐两个人，选择的策略就是要最大限度减少总时间。主要策略有以下几种：

  1. 最快的两人反复往返：让最快的两个人来回渡船，因为他们的渡河时间最短，能有效减少船的回程时间。

  2. 让最慢的两人一次性过河：让最慢的两人一次性过河，减少他们的往返次数。

  • 具体解法： 为了求最短时间，我们可以采用以下步骤：

  1. 先让速度最快的两个过河（即1分钟和2分钟），此时船在B点。

    • 过河时间：2分钟。

  2. 让速度最快的那个人（即1分钟）把船开回A点。

    • 回程时间：1分钟。

  3. 然后让速度最慢的两个人（即4分钟和8分钟）一起过河。

    • 过河时间：8分钟。

  4. 让速度较快的那个人（即2分钟）把船开回A点。

    • 回程时间：2分钟。

  5. 最后，让速度最快的两个人（即1分钟和2分钟）再过河。

    • 过河时间：2分钟。
  • 总时间： [ 2 + 1 + 8 + 2 + 2 = 15 \text{分钟} ]

所以，这四个人最短的过河时间为 15分钟，选择答案 B。

  • 总结： 这个问题使用贪心算法（Greedy Algorithm）是最有效的解法。通过将最快的人作为来回的船夫，并尽量减少慢速人的往返次数，能够有效地缩短过河时间。
上次更新: 2024-10-19 10:01:51

分治算法