C++贪心算法教程（0基础入门）

一、什么是贪心算法？

贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的解题策略。

核心思想：不考虑整体最优，只追求局部最优。通过一系列局部最优选择，最终得到全局最优解（但并非所有问题都适用）。

生活中的贪心例子：

• 找零钱时，先拿面额最大的货币
• 行程规划时，每次选择最近的下一个地点

二、贪心算法的适用条件

1. 贪心选择性质：局部最优选择能导致全局最优解
2. 最优子结构：问题的最优解包含子问题的最优解

注意：很多问题不能用贪心算法解决（如背包问题），需要根据问题特性判断。

三、贪心算法的基本步骤

1. 确定问题的最优子结构
2. 设计贪心策略（即如何选择局部最优）
3. 证明该策略能得到全局最优解
4. 实现算法

四、经典例题详解

例题1：找零钱问题

问题：用最少的硬币凑出指定金额，硬币面额为1、5、10、25。

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 函数功能：用最少硬币凑出金额
// 参数：coins-硬币面额数组，amount-目标金额
// 返回值：最少硬币数量
int coinChange(vector<int>& coins, int amount) {
    // 排序硬币面额（从大到小）
    sort(coins.rbegin(), coins.rend());
    
    int count = 0;  // 记录硬币数量
    int remaining = amount;  // 剩余需要凑的金额
    
    for (int coin : coins) {
        // 如果当前硬币面额小于等于剩余金额，就使用它
        while (remaining >= coin) {
            remaining -= coin;  // 减去当前硬币面额
            count++;            // 硬币数量加1
            cout << "使用" << coin << "元硬币，剩余" << remaining << "元" << endl;
        }
        // 如果已凑够金额，提前退出
        if (remaining == 0) break;
    }
    
    // 如果无法凑出目标金额，返回-1
    return remaining == 0 ? count : -1;
}

int main() {
    vector<int> coins = {1, 5, 10, 25};  // 硬币面额
    int amount = 37;                     // 目标金额
    
    int result = coinChange(coins, amount);
    
    if (result != -1) {
        cout << "凑出" << amount << "元最少需要" << result << "枚硬币" << endl;
    } else {
        cout << "无法凑出" << amount << "元" << endl;
    }
    
    return 0;
}

输出结果：

使用25元硬币，剩余12元
使用10元硬币，剩余2元
使用1元硬币，剩余1元
使用1元硬币，剩余0元
凑出37元最少需要4枚硬币

例题2：活动选择问题

问题：有n个活动，每个活动有开始时间和结束时间，如何选择最多的互不冲突的活动？

贪心策略：每次选择结束时间最早的活动。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义活动结构体
struct Activity {
    int start;  // 开始时间
    int end;    // 结束时间
    int id;     // 活动编号
    
    // 构造函数
    Activity(int s, int e, int i) : start(s), end(e), id(i) {}
};

// 排序函数：按结束时间从小到大排序
bool compare(const Activity& a, const Activity& b) {
    return a.end < b.end;
}

// 函数功能：选择最多的不冲突活动
void selectActivities(vector<Activity>& activities) {
    // 按结束时间排序
    sort(activities.begin(), activities.end(), compare);
    
    vector<Activity> selected;  // 存储选中的活动
    
    // 选择第一个活动（结束时间最早的）
    selected.push_back(activities[0]);
    int lastEnd = activities[0].end;  // 记录最后一个选中活动的结束时间
    
    // 遍历剩余活动
    for (size_t i = 1; i < activities.size(); i++) {
        // 如果当前活动的开始时间 >= 最后一个选中活动的结束时间
        if (activities[i].start >= lastEnd) {
            selected.push_back(activities[i]);
            lastEnd = activities[i].end;  // 更新最后结束时间
        }
    }
    
    // 输出结果
    cout << "选中的活动有：";
    for (const Activity& a : selected) {
        cout << "活动" << a.id << "(" << a.start << "-" << a.end << ") ";
    }
    cout << endl;
    cout << "共选中" << selected.size() << "个活动" << endl;
}

int main() {
    // 创建活动列表
    vector<Activity> activities;
    activities.emplace_back(1, 4, 1);   // 活动1：1-4点
    activities.emplace_back(3, 5, 2);   // 活动2：3-5点
    activities.emplace_back(0, 6, 3);   // 活动3：0-6点
    activities.emplace_back(5, 7, 4);   // 活动4：5-7点
    activities.emplace_back(3, 9, 5);   // 活动5：3-9点
    activities.emplace_back(5, 9, 6);   // 活动6：5-9点
    activities.emplace_back(6, 10, 7);  // 活动7：6-10点
    activities.emplace_back(8, 11, 8);  // 活动8：8-11点
    activities.emplace_back(8, 12, 9);  // 活动9：8-12点
    activities.emplace_back(2, 14, 10); // 活动10：2-14点
    activities.emplace_back(12, 16, 11);// 活动11：12-16点
    
    selectActivities(activities);
    
    return 0;
}

输出结果：

选中的活动有：活动1(1-4) 活动4(5-7) 活动8(8-11) 活动11(12-16) 
共选中4个活动

例题3：区间覆盖问题

问题：用最少的区间覆盖指定线段[start, end]。

贪心策略：每次选择能覆盖当前未覆盖部分且延伸最远的区间。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 区间结构体
struct Interval {
    int left;   // 左端点
    int right;  // 右端点
    
    Interval(int l, int r) : left(l), right(r) {}
};

// 排序函数：按左端点从小到大排序
bool compare(const Interval& a, const Interval& b) {
    return a.left < b.left;
}

// 函数功能：用最少区间覆盖[targetStart, targetEnd]
int coverLine(vector<Interval>& intervals, int targetStart, int targetEnd) {
    // 排序区间
    sort(intervals.begin(), intervals.end(), compare);
    
    int count = 0;          // 选中的区间数量
    int currentEnd = targetStart;  // 当前已覆盖到的位置
    int nextEnd = currentEnd;      // 下一步能覆盖到的最远位置
    int i = 0;              // 当前检查的区间索引
    int n = intervals.size();
    
    while (currentEnd < targetEnd) {
        // 找到所有左端点 <= 当前已覆盖位置的区间，选择其中右端点最大的
        while (i < n && intervals[i].left <= currentEnd) {
            nextEnd = max(nextEnd, intervals[i].right);
            i++;
        }
        
        // 如果无法再延伸，说明不能完全覆盖
        if (nextEnd == currentEnd) {
            return -1;
        }
        
        currentEnd = nextEnd;  // 更新已覆盖位置
        count++;               // 区间数量加1
    }
    
    return count;
}

int main() {
    // 创建区间列表
    vector<Interval> intervals;
    intervals.emplace_back(1, 4);
    intervals.emplace_back(2, 5);
    intervals.emplace_back(3, 6);
    intervals.emplace_back(5, 7);
    intervals.emplace_back(8, 10);
    intervals.emplace_back(9, 12);
    
    int targetStart = 1;  // 目标线段起点
    int targetEnd = 12;   // 目标线段终点
    
    int result = coverLine(intervals, targetStart, targetEnd);
    
    if (result != -1) {
        cout << "覆盖线段[" << targetStart << "," << targetEnd << "]最少需要" << result << "个区间" << endl;
    } else {
        cout << "无法完全覆盖线段[" << targetStart << "," << targetEnd << "]" << endl;
    }
    
    return 0;
}

输出结果：

覆盖线段[1,12]最少需要3个区间

五、贪心算法的优缺点

优点：

• 简单直观，容易实现
• 时间复杂度低，效率高

缺点：

• 不是所有问题都适用
• 难以证明正确性
• 可能得到局部最优而非全局最优

六、练习题

1. 柠檬水找零：顾客排队买柠檬水，每杯5元。顾客支付5元、10元或20元，初始没有零钱，判断能否给所有顾客找零。
2. 分发饼干：每个孩子有一个饥饿度，每个饼干有一个大小，一个饼干只能给一个孩子，且饼干大小必须>=饥饿度，求最多能满足几个孩子。
3. 摆动序列：一个整数序列，相邻元素的差正负交替，求最长摆动子序列的长度。

通过以上内容，你应该对贪心算法有了基本了解。贪心算法的关键在于找到合适的贪心策略，多做练习才能熟练掌握如何设计和应用贪心算法。