贪心算法介绍

贪心算法在每一步都做出当前看起来最优的选择。形式化地描述如下：

$$\text{选择函数: } f(x) = \text{局部最优选择}$$

如果一个问题满足以下两个条件，则贪心算法能够得到全局最优解：

1. 贪心选择性质：局部最优的选择最终可以达到全局最优。
2. 最优子结构：问题的最优解包含其子问题的最优解。

• 贪心算法概念

  贪心算法（Greedy Algorithm）是一种算法设计思想，其基本策略是在每一步选择中都采取在当前看来最优的选择（即局部最优解），从而期望导致全局最优解。这种方法不回溯，不重新考虑已经做出的决策。

• 贪心算法的主要特点

  • 局部最优选择 ：每次都选择最有利的局部决策。
  • 不可回溯 ：一旦做出选择，后续不会再回溯修改。
  • 适用问题要求 ：只有当问题满足“贪心选择性质”与“最优子结构”时，贪心算法才能得到全局最优解。

• 与动态规划的比较

  • 贪心算法 ：只关注当前最优解，计算量少，适用于结构简单且满足贪心性质的问题。
  • 动态规划 ：考虑所有子问题的可能性，通过保存子问题的解来构造全局最优解，适用于问题存在重叠子问题或贪心解法不一定正确的情况。

• 经典示例——活动选择问题

  • 问题描述 ：给定一组活动，每个活动都有开始时间和结束时间，要求在不重叠的前提下选出最多的活动。
  • 贪心策略 ：每次选择结束时间最早的活动，这样可以留出更多时间安排后续活动。

例如，活动选择问题的贪心策略为：

$$\text{选取结束时间最早的活动}$$

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

struct Activity {
    int start, end;
};

// 按照活动结束时间排序
bool compare(Activity a, Activity b) {
    return a.end < b.end;
}

int activitySelection(std::vector<Activity>& activities) {
    // 排序：使得结束时间较早的活动排在前面
    std::sort(activities.begin(), activities.end(), compare);
  
    int count = 0;
    int lastEndTime = 0;
  
    // 遍历所有活动，选择不冲突的活动
    for (auto& act : activities) {
        if (act.start >= lastEndTime) {
            count++;
            lastEndTime = act.end;
        }
    }
    return count;
}

int main() {
    std::vector<Activity> activities = { {1, 3}, {2, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9} };
    std::cout << "最多活动数量: " << activitySelection(activities) << std::endl;
    return 0;
}

总结

贪心算法因其简单和高效在某些问题上表现优异，但并不适用于所有情况。使用前需要验证问题是否满足贪心选择性质和最优子结构性质，确保局部最优解能合并成全局最优解。