C++ 贪心算法入门教程

贪心算法是一种在每一步选择中都采取当前状态下最优（局部最优）选择，从而希望导致全局结果也最优的算法策略。虽然贪心算法不能解决所有问题，但它可以高效解决许多经典问题。

1. 贪心算法基本思想

贪心算法的核心思想是：每一步都做出当前看起来最好的选择，而不考虑这种选择对未来的影响。这种策略在某些问题中可以直接得到全局最优解，但在其他问题中可能只能得到近似解。

2. 贪心算法适用条件

贪心算法适用于满足以下两个条件的问题：

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

3. 简单示例：找零问题

问题描述：假设你是一个收银员，需要找给顾客一定金额的零钱，如何使用最少的硬币？

示例代码：

#include <iostream>
#include <vector>
using namespace std; // 使用标准命名空间，避免重复写std::

// 找零问题的贪心算法实现
vector<int> greedyChange(int amount) {
    vector<int> coins = {25, 10, 5, 1}; // 硬币面额：25美分(quarter)、10美分(dime)、5美分(nickel)、1美分(penny)
    vector<int> result(coins.size(), 0); // 每种硬币的数量
    
    for (int i = 0; i < coins.size(); i++) {
        // 尽可能多地使用当前最大面额的硬币
        result[i] = amount / coins[i];
        amount = amount % coins[i]; // 剩余需要找零的金额
    }
    
    return result;
}

int main() {
    int amount = 63; // 需要找零63美分
    vector<int> change = greedyChange(amount);
    
    cout << "找零 " << amount << " 美分需要的硬币数量：" << endl;
    vector<int> coins = {25, 10, 5, 1};
    
    for (int i = 0; i < coins.size(); i++) {
        if (change[i] > 0) {
            cout << coins[i] << "美分: " << change[i] << "个" << endl;
        }
    }
    
    return 0;
}

代码解释：

• 硬币面额数组 coins 包含四种美国硬币面额（25、10、5、1美分）。
• 贪心策略：每次都选择当前可用的最大面额硬币，直到剩余金额为0。
• 结果验证：对于63美分的找零，算法会返回2个25美分、1个10美分和3个1美分，共6个硬币，这是最优解。

4. 进阶示例：活动选择问题

问题描述：有多个活动需要使用同一资源（如会议室），每个活动有开始时间和结束时间，如何选择最多的活动，使得它们互不冲突？

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; // 使用标准命名空间，避免重复写std::

// 活动结构体，包含活动编号、开始时间和结束时间
struct Activity {
    int id;
    int start;
    int end;
};

// 比较函数，按结束时间升序排序
bool compareActivities(const Activity& a, const Activity& b) {
    return a.end < b.end;
}

// 活动选择的贪心算法实现
vector<int> activitySelection(vector<Activity>& activities) {
    // 按结束时间排序
    sort(activities.begin(), activities.end(), compareActivities);
    
    vector<int> selected;
    if (activities.empty()) return selected;
    
    // 选择第一个结束的活动
    selected.push_back(activities[0].id);
    int lastEndTime = activities[0].end;
    
    // 遍历剩余活动，选择开始时间晚于上一个结束时间的活动
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].start >= lastEndTime) {
            selected.push_back(activities[i].id);
            lastEndTime = activities[i].end;
        }
    }
    
    return selected;
}

int main() {
    // 示例活动：(编号, 开始时间, 结束时间)
    vector<Activity> activities = {
        {1, 1, 4}, {2, 3, 5}, {3, 0, 6}, {4, 5, 7},
        {5, 3, 9}, {6, 5, 9}, {7, 6, 10}, {8, 8, 11},
        {9, 8, 12}, {10, 2, 14}, {11, 12, 16}
    };
    
    vector<int> selected = activitySelection(activities);
    
    cout << "最多可以选择的活动数量：" << selected.size() << endl;
    cout << "选择的活动编号为：";
    for (int id : selected) {
        cout << id << " ";
    }
    cout << endl;
    
    return 0;
}

代码解释：

• 活动结构体 Activity 存储每个活动的编号、开始时间和结束时间。
• 贪心策略：每次选择结束时间最早且与已选活动不冲突的活动。
• 排序操作：首先按结束时间对活动进行排序，确保每次能选择最早结束的活动。

5. 贪心算法的优缺点

优点：

• 算法简单，易于理解和实现。
• 时间复杂度通常较低，效率高。

缺点：

• 不能解决所有问题，只适用于满足贪心选择性质的问题。
• 有时得到的解只是近似最优解，而非全局最优解。

6. 练习题

1. 分数背包问题：给定一组物品，每个物品有重量和价值，以及一个容量为C的背包，如何选择物品放入背包，使得背包中物品的总价值最大？注意：物品可以分割。

2. 最小等待时间问题：有n个任务需要处理，每个任务需要一定的时间，如何安排处理顺序，使得所有任务的平均等待时间最短？

3. 跳跃游戏：给定一个非负整数数组，每个元素代表在该位置可以跳跃的最大长度，判断是否可以跳到数组的最后一个位置。

通过这些示例和练习，你应该对贪心算法有了基本的理解。贪心算法虽然简单，但在合适的问题中可以发挥很大作用。在实际应用中，需要仔细分析问题是否满足贪心选择性质，避免盲目使用贪心策略导致错误结果。