贪心算法是一种在每一步选择中都采取当前状态下最优（最有利）的选择，从而希望导致结果是全局最优的算法。贪心算法并不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。下面为你详细介绍 C++ 中贪心算法的相关内容。

算法原理

贪心算法的基本步骤如下：

1. 分解问题：将原问题分解为若干个子问题。
2. 贪心选择：在每一步选择中，都选择当前看起来最优的解决方案，而不考虑该选择对后续步骤的影响。
3. 求解子问题：对每个子问题都做出贪心选择，逐步构建出问题的解。
4. 组合解：将每一步的选择组合起来，得到原问题的最终解。

适用条件

贪心算法适用的问题需要满足以下两个性质：

• 贪心选择性质：问题的全局最优解可以通过一系列局部最优选择得到。也就是说，在每一步选择中，只需要考虑当前的最优选择，而不需要考虑子问题的解。
• 最优子结构性质：问题的最优解包含其子问题的最优解。即原问题的最优解可以由子问题的最优解组合而成。

示例：活动选择问题

活动选择问题是一个经典的贪心算法应用场景。假设有多个活动，每个活动有开始时间和结束时间，要求在这些活动中选择出最多的互不冲突的活动。

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

// 定义活动结构体
struct Activity {
    int start;
    int end;
};

// 比较函数，按照活动结束时间排序
bool compareActivities(const Activity& a1, const Activity& a2) {
    return a1.end < a2.end;
}

// 活动选择函数
std::vector<int> activitySelection(const std::vector<Activity>& activities) {
    int n = activities.size();
    std::vector<int> selectedActivities;

    // 按照活动结束时间排序
    std::vector<Activity> sortedActivities = activities;
    std::sort(sortedActivities.begin(), sortedActivities.end(), compareActivities);

    // 选择第一个活动
    selectedActivities.push_back(0);
    int lastEndTime = sortedActivities[0].end;

    // 遍历剩余活动
    for (int i = 1; i < n; ++i) {
        if (sortedActivities[i].start >= lastEndTime) {
            selectedActivities.push_back(i);
            lastEndTime = sortedActivities[i].end;
        }
    }

    return selectedActivities;
}

int main() {
    std::vector<Activity> activities = {
        {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9},
        {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}
    };

    std::vector<int> selectedActivities = activitySelection(activities);

    std::cout << "Selected activities:" << std::endl;
    for (int index : selectedActivities) {
        std::cout << "Activity " << index << ": [" << activities[index].start << ", " << activities[index].end << "]" << std::endl;
    }

    return 0;
}

代码解释

1. 结构体 Activity：用于存储每个活动的开始时间和结束时间。
2. 比较函数 compareActivities：用于对活动按照结束时间进行排序。
3. 活动选择函数 activitySelection：
   • 首先对活动按照结束时间进行排序。
   • 选择第一个活动，并记录其结束时间。
   • 遍历剩余活动，若某个活动的开始时间大于等于上一个选择的活动的结束时间，则选择该活动，并更新最后一个活动的结束时间。
4. 主函数 main：定义了一系列活动，并调用 activitySelection 函数选择出最多的互不冲突的活动，最后输出选择的活动。

复杂度分析

• 时间复杂度：排序操作的时间复杂度为 $O(n log n)$，遍历活动的时间复杂度为 $O(n)$，因此总的时间复杂度为 $O(n log n)$。
• 空间复杂度：主要用于存储排序后的活动和选择的活动，空间复杂度为 $O(n)$。

注意事项

• 贪心算法并不适用于所有问题，只有满足贪心选择性质和最优子结构性质的问题才能使用贪心算法求解。
• 在使用贪心算法时，需要证明每一步的贪心选择能够得到全局最优解，否则可能得到的只是局部最优解。