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

c++中如何实现贪心算法选择问题_c++贪心算法选择问题实现方法

尼克

发布： 2025-10-07 13:13:01

原创

212人浏览过

贪心算法通过每步选择最早结束的活动来最大化不冲突活动数量，C++实现包括定义活动结构体、按结束时间排序并遍历选择兼容活动，时间复杂度O(n log n)，适用于满足贪心选择性质的问题。

c++中如何实现贪心算法选择问题_c++贪心算法选择问题实现方法

贪心算法在C++中解决选择问题的核心是：每一步都做出当前最优的选择，希望最终结果是全局最优。针对“选择问题”，比如活动选择、区间调度等，贪心策略通常有效且实现简单。

活动选择问题描述

给定n个活动，每个活动有开始时间start和结束时间end，一个人在同一时间只能做一件事。目标是选出最多互不冲突的活动数量。

贪心策略：按结束时间升序排序，优先选择最早结束的活动，这样可以为后续活动留出更多时间。

实现步骤

以下是C++中的具体实现方法：

法语写作助手

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

查看详情

1. 定义活动结构体，包含开始和结束时间 2. 按结束时间对活动排序 3. 遍历活动列表，选择与上一个选中活动不冲突的活动

C++代码示例

#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 << "选中的活动：" << endl;
    int i = 0;
    cout << "[" << activities[i].start << ", " << activities[i].end << "]" << endl;

    // 遍历剩余活动
    for (int j = 1; j < activities.size(); j++) {
        // 如果当前活动的开始时间大于等于上一个选中活动的结束时间
        if (activities[j].start >= activities[i].end) {
            cout << "[" << activities[j].start << ", " << activities[j].end << "]" << endl;
            i = j;  // 更新最后选中的活动
        }
    }
}

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

登录后复制