c++中如何实现贪心算法_c++贪心算法实现方法-C++-PHP中文网

c++中如何实现贪心算法_c++贪心算法实现方法

尼克

发布： 2025-09-28 20:09:02

原创

227人浏览过

贪心算法通过每步选择当前最优解以期望达到全局最优，适用于具有贪心选择性质和最优子结构的问题。

c++中如何实现贪心算法_c++贪心算法实现方法

贪心算法是一种在每一步选择中都采取当前状态下最优的选择，希望最终结果是全局最优的策略。它不回溯，也不考虑未来的影响，只关注眼前最优。C++中实现贪心算法的关键在于明确问题是否适合贪心策略，并设计合理的贪心规则。

贪心算法的基本思路

贪心算法通常适用于具有“贪心选择性质”和“最优子结构”的问题。也就是说，局部最优解能导致全局最优解。常见应用场景包括：活动选择、区间调度、最小生成树（Prim、Kruskal）、霍夫曼编码、找零钱等。

实现步骤：

将问题分解为子问题
定义贪心策略（如按结束时间排序）
依次处理每个子问题，做出当前最优选择
合并结果

以活动选择问题为例

假设有n个活动，每个活动有开始时间和结束时间，目标是选出最多互不冲突的活动。

立即学习“C++免费学习笔记（深入）”；

法语写作助手

法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。

查看详情

贪心策略： 按照活动的结束时间升序排列，优先选择最早结束的活动。

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

using namespace std;

struct Activity {
    int start, end;
};

// 比较函数：按结束时间排序
bool compare(Activity a, Activity b) {
    return a.end < b.end;
}

void selectActivities(vector<Activity>& activities) {
    // 按结束时间排序
    sort(activities.begin(), activities.end(), compare);

    cout << "Selected activities:\n";
    int i = 0;
    cout << "[" << activities[i].start << ", " << activities[i].end << "]\n";

    // 遍历其余活动，选择与上一个不冲突的
    for (int j = 1; j < activities.size(); j++) {
        if (activities[j].start >= activities[i].end) {
            cout << "[" << activities[j].start << ", " << activities[j].end << "]\n";
            i = j;
        }
    }
}

int main() {
    vector<Activity> acts = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    selectActivities(acts);
    return 0;
}

登录后复制

输出结果会是最早结束且不重叠的活动序列，比如 [1,4], [5,7], [8,9]。