20260228 143225 Cpp 入门第十七课

第十七章：贪心算法——每次都选最好的 ¶

你好！欢迎来到第十七章！在生活中，我们经常要做选择：吃自助餐时，是先吃喜欢的菜还是随便拿？去游乐场玩，是先玩排队时间长的项目还是短的？贪心算法就是一种“每次都选当前最好的”的策略。虽然不一定能得到全局最优解，但在很多问题上却非常有效。这一章我们就来学习贪心算法，看看什么时候可以“贪心”。

17.1 贪心算法程序范例 ¶

先来看一个最简单的贪心问题：找零钱问题。假设我们需要用最少的硬币数量凑出一定的金额，硬币面额有 1元、2元、5元、10元。贪心策略是：每次都尽量用面额最大的硬币。

#include <iostream>
using namespace std;

int main() {
    int amount;
    cout << "请输入金额（元）：";
    cin >> amount;

    int coins[] = {10, 5, 2, 1};   // 硬币面额，从大到小排序
    int count = 0;

    for (int i = 0; i < 4; i++) {
        int num = amount / coins[i];   // 用多少枚当前面额的硬币
        count += num;
        amount -= num * coins[i];
        if (num > 0) {
            cout << "需要" << coins[i] << "元硬币：" << num << "枚" << endl;
        }
    }
    cout << "总共需要" << count << "枚硬币" << endl;
    return 0;
}

运行示例（输入17）：

需要10元硬币：1枚
需要5元硬币：1枚
需要2元硬币：1枚
总共需要3枚硬币

这里我们每次都用最大面额的硬币，这就是贪心：在当前步，选择当前最好的（面额最大的），最终得到了最少硬币数。注意，这个策略对这套面额有效，但如果面额是 1、3、4 元，要凑 6 元，贪心会先选4，再选1和1，共3枚，但最优是 3+3 只用2枚，说明贪心不一定总是最优。所以我们用贪心时要先确认问题是否适合贪心。

17.2 贪心算法的用法 ¶

17.2.1 什么是贪心算法？¶

贪心算法（Greedy Algorithm）是指在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。就像吃自助餐时，每次都拿自己最喜欢的菜，不一定能吃得最健康，但能吃得最开心。

贪心算法通常用于求解最优化问题，比如找最少硬币、安排最多活动、求最短路径等。

17.2.2 贪心算法的特点 ¶

局部最优：每一步都选当前最优的。
不可回溯：一旦做出选择，就不再改变。
不一定得到全局最优：需要问题具有贪心选择性质（即局部最优能导致全局最优）。

17.2.3 贪心算法的适用条件 ¶

贪心选择性质：可以通过局部最优选择来得到全局最优解。
最优子结构性质：问题的最优解包含子问题的最优解。

17.2.4 贪心算法的一般步骤 ¶

建立数学模型来描述问题。
把问题分解成若干个子问题。
对每个子问题，按照某种规则（贪心策略）做出当前最优选择。
把所有子问题的局部最优解合成原问题的一个解。

17.3 编程实例讲解 ¶

实例1：活动安排问题 ¶

题目：有若干个活动，每个活动有开始时间和结束时间。如何安排活动，使得能参加的活动数量最多？（假设同一时间只能参加一个活动）

贪心策略：按结束时间最早的活动优先选择。因为结束早，留给后面的时间就多。

#include <iostream>
#include <algorithm>   // 用到sort
using namespace std;

struct Activity {
    int start;
    int end;
};

// 按结束时间升序排序
bool cmp(Activity a, Activity b) {
    return a.end < b.end;
}

int main() {
    int n;
    cout << "请输入活动个数：";
    cin >> n;
    Activity acts[100];
    for (int i = 0; i < n; i++) {
        cin >> acts[i].start >> acts[i].end;
    }

    // 按结束时间排序
    sort(acts, acts + n, cmp);

    int count = 1;               // 至少选第一个活动
    int lastEnd = acts[0].end;   // 上一个活动的结束时间

    for (int i = 1; i < n; i++) {
        if (acts[i].start >= lastEnd) {   // 如果当前活动开始时间在上一个活动结束后
            count++;
            lastEnd = acts[i].end;
        }
    }

    cout << "最多可以参加" << count << "个活动" << endl;
    return 0;
}

输入示例：

输出：最多可以参加3个活动（比如选 1-3, 4-7, 8-10）。

实例2：背包问题（部分背包）¶

题目：有一个背包，容量为C。有n种物品，每种物品有重量 w[i] 和价值 v[i]。可以只取一部分（比如切分），问如何装使得总价值最大？

贪心策略：按单位重量价值（v[i]/w[i]）从高到低选取，优先装价值率高的物品。

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

struct Item {
    int weight;
    int value;
    double ratio;   // 单位重量价值
};

bool cmp(Item a, Item b) {
    return a.ratio > b.ratio;
}

int main() {
    int n, capacity;
    cout << "请输入物品数量和背包容量：";
    cin >> n >> capacity;
    Item items[100];
    for (int i = 0; i < n; i++) {
        cin >> items[i].weight >> items[i].value;
        items[i].ratio = (double)items[i].value / items[i].weight;
    }

    sort(items, items + n, cmp);   // 按价值率降序

    double totalValue = 0;
    int remaining = capacity;

    for (int i = 0; i < n; i++) {
        if (items[i].weight <= remaining) {
            // 可以全拿
            totalValue += items[i].value;
            remaining -= items[i].weight;
        } else {
            // 只能拿一部分
            totalValue += items[i].ratio * remaining;
            break;
        }
    }

    cout << "最大总价值：" << totalValue << endl;
    return 0;
}

注意：这是部分背包问题（物品可分割），贪心有效。如果是0-1背包（物品不可分割），贪心不一定最优，需要用动态规划。

实例3：排队打水问题 ¶

题目：有n个人排队打水，每个人打水需要的时间不同。如何安排打水顺序，使得所有人等待的总时间最少？

贪心策略：让打水时间短的人先打。因为这样后面的人等待时间总和最小。

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

int main() {
    int n;
    cout << "请输入人数：";
    cin >> n;
    int times[100];
    for (int i = 0; i < n; i++) {
        cin >> times[i];
    }

    sort(times, times + n);   // 升序排序

    int totalWait = 0;
    int currentTime = 0;
    for (int i = 0; i < n; i++) {
        totalWait += currentTime;      // 第i个人等待的时间
        currentTime += times[i];       // 当前累计时间
    }

    cout << "总等待时间：" << totalWait << endl;
    return 0;
}

实例4：删数问题 ¶

题目：给定一个数字字符串（如 “1432219”），删除 k 个数字，使得剩下的数字最小（保持相对顺序）。

贪心策略：从左到右遍历，如果当前数字比下一个数字大，就删除当前数字，这样能让高位变小。

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

string removeKdigits(string num, int k) {
    string result;
    for (char digit : num) {
        while (!result.empty() && result.back() > digit && k > 0) {
            result.pop_back();   // 删除前面比当前大的数
            k--;
        }
        result.push_back(digit);
    }
    // 如果还有剩余删除次数，从末尾删
    while (k > 0 && !result.empty()) {
        result.pop_back();
        k--;
    }
    // 去除前导零
    int start = 0;
    while (start < result.size() && result[start] == '0') start++;
    if (start == result.size()) return "0";
    return result.substr(start);
}

int main() {
    string num;
    int k;
    cout << "请输入数字字符串和要删除的个数：";
    cin >> num >> k;
    cout << "删除后最小的数字：" << removeKdigits(num, k) << endl;
    return 0;
}

17.4 阶段性编程练习 ¶

练习1：用贪心算法解决找零钱问题，硬币面额包括 1、5、10、20、50、100，凑出指定金额，输出每种硬币的数量。
练习2：有 n 个任务，每个任务有截止时间和收益，每个任务耗时1个单位时间。如何安排任务使得总收益最大？（提示：按收益降序，尽量放在截止时间前完成）
练习3：区间覆盖问题：给定一个线段区间 [s, t] 和若干条线段，选择最少的线段覆盖整个区间。（提示：按左端点排序，每次选能覆盖当前起点的最右端点）
练习4：小船过河问题：n 个人要过河，只有一条船，每次最多载两人，每个人过河时间不同，求所有人过河的最短总时间。（经典贪心问题，有两种策略）
练习5：哈夫曼编码思想：给定一些字符及其出现频率，构造哈夫曼树（用优先队列模拟）。