贪心算法：用局部最优解迈向全局最优的艺术

贪心算法：用局部最优解迈向全局最优的艺术

什么是贪心算法？

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法策略。它不像动态规划那样考虑所有可能的子问题，而是局部最优，希望全局最优。

贪心算法的适用场景

贪心算法适用于满足以下两个条件的问题：

1. 贪心选择性质：局部最优选择能导致全局最优解

2. 最优子结构：问题的最优解包含其子问题的最优解

经典问题与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;
}