贪心算法：用局部最优解迈向全局最优的艺术
什么是贪心算法？
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法策略。它不像动态规划那样考虑所有可能的子问题，而是局部最优，希望全局最优。
贪心算法的适用场景
贪心算法适用于满足以下两个条件的问题：
贪心选择性质：局部最优选择能导致全局最优解
最优子结构：问题的最优解包含其子问题的最优解
经典问题与C++实现
1. 找零钱问题（硬币问题）
问题描述：给定不同面额的硬币和一个总金额，求最少硬币数。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int coinChangeGreedy(vector<int>& coins, int amount) {
// 从大到小排序硬币
sort(coins.rbegin(), coins.rend());
int count = 0;
for (int coin : coins) {
while (amount >= coin) {
amount -= coin;
count++;
}
}
return (amount == 0) ? count : -1;
}
int main() {
vector<int> coins = {1, 5, 10, 20, 50, 100};
int amount = 123;
int result = coinChangeGreedy(coins, amount);
if (result != -1) {
cout << "找零 " << amount << " 元需要最少 " << result << " 枚硬币" << endl;
} else {
cout << "无法找零" << endl;
}
return 0;
}
2. 区间调度问题
问题描述：给定多个会议的开始和结束时间，求最多能参加多少个不冲突的会议。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Interval {
int start;
int end;
};
bool compare(Interval a, Interval b) {
return a.end < b.end; // 按结束时间升序排序
}
int maxMeetings(vector<Interval>& meetings) {
if (meetings.empty()) return 0;
// 按结束时间排序
sort(meetings.begin(), meetings.end(), compare);
int count = 1; // 第一个会议总是可以参加
int lastEnd = meetings[0].end;
for (int i = 1; i < meetings.size(); i++) {
if (meetings[i].start >= lastEnd) {
count++;
lastEnd = meetings[i].end;
}
}
return count;
}
int main() {
vector<Interval> meetings = {
{1, 3}, {2, 4}, {3, 6}, {5, 7}, {8, 9}
};
int result = maxMeetings(meetings);
cout << "最多可以参加 " << result << " 个会议" << endl;
return 0;
}
