数据结构刷题之贪心算法

贪心算法（Greedy Algorithm）

是一种在每个步骤中都选择当前最优解的算法设计策略。它通常用于解决优化问题，例如最小化成本或最大化收益。贪心算法的核心思想是：在每一步选择中，都做出局部最优的选择，希望最终能得到全局最优解。

贪心算法的特点

贪心选择性质:
一个问题的整体最优解可以通过一系列局部最优选择来构造。
每次选择只依赖于当前状态，而不考虑未来的影响。
最优子结构性质:
一个问题的最优解包含其子问题的最优解。
简单高效:
贪心算法通常比动态规划等方法更简单、更高效，但适用范围有限。

经典题目

1.找零问题
给定不同面额的硬币和一个总金额，要求使用最少数量的硬币凑出该金额。
分析一下这个问题：这种问题肯定是先使用大的去找，大的找不完采用晓得，典型的局部最优解–>整体最优解
思路先用大的找->再用小的找

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int minCoins(vector<int>& coins, int amount) {// 对硬币面额从大到小排序sort(coins.begin(), coins.end(), greater<int>());int count = 0; // 记录硬币数量for (int coin : coins) {if (amount == 0) break; // 如果金额为 0，结束循环count += amount / coin; // 使用当前面额的硬币尽可能多amount %= coin;         // 更新剩余金额}return amount == 0 ? count : -1; // 如果无法找零，返回 -1
}int main() {vector<int> coins = {1, 5, 10, 25}; // 硬币面额int amount;cout << "请输入总金额: ";cin >> amount;int result = minCoins(coins, amount);if (result != -1) {cout << "最少需要 " << result << " 枚硬币。" << endl;} else {cout << "无法找零。" << endl;}return 0;
}```
2. 活动选择问题
给定一组活动及其开始时间和结束时间，求最多能参加多少个不重叠的活动。
对于活动选择问题，贪心策略通常是优先选择结束时间最早的活动。原因如下：
如果一个活动的结束时间较早，那么它留下的时间窗口就更大，从而为后续活动提供了更多可能的选择。
这种策略确保每次选择都尽可能地为后续活动腾出空间，从而最大化可参加的活动数量。
```cpp
#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;
}int maxActivities(vector<Activity>& activities) {// 按结束时间排序sort(activities.begin(), activities.end(), compare);int count = 1; // 至少可以选择第一个活动int lastEnd = activities[0].end;for (int i = 1; i < activities.size(); ++i) {if (activities[i].start >= lastEnd) { // 如果当前活动与上一个活动不冲突count++;lastEnd = activities[i].end; // 更新最后一个活动的结束时间}}return count;
}int main() {vector<Activity> activities = {{1, 3}, {2, 5}, {4, 7}, {6, 9}};cout << "最多可以参加 " << maxActivities(activities) << " 个活动。" << endl;return 0;
}

3. 分糖果问题
   有若干孩子和糖果，每个孩子有一个贪婪因子（表示至少需要多少糖果才能满足），每个糖果有一个大小。问最多能满足多少孩子？
   策略：
   优先满足需求最小的孩子：因为需求小的孩子更容易被满足，这样可以腾出更多较大的糖果来满足其他孩子。
   优先使用最小的糖果：因为较小的糖果可能无法满足需求大的孩子，但可以满足需求小的孩子。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int findContentChildren(vector<int>& g, vector<int>& s) {// 对孩子的贪婪因子和糖果大小进行排序sort(g.begin(), g.end());sort(s.begin(), s.end());int child = 0, cookie = 0;while (child < g.size() && cookie < s.size()) {if (s[cookie] >= g[child]) { // 如果当前糖果可以满足孩子child++; // 满足的孩子数加 1}cookie++; // 移动到下一个糖果}return child; // 返回满足的孩子数
}int main() {vector<int> g = {1, 2, 3}; // 孩子的贪婪因子vector<int> s = {1, 1};    // 糖果的大小cout << "最多可以满足 " << findContentChildren(g, s) << " 个孩子。" << endl;return 0;
}

4. 最优装载问题
   有一艘船，载重量为 W，有若干货物，每个货物有重量 w[i]。求最多能装多少货物。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int maxLoad(vector<int>& weights, int W) {// 按货物重量从小到大排序sort(weights.begin(), weights.end());int count = 0; // 记录装入的货物数量for (int weight : weights) {if (W >= weight) { // 如果还能装下当前货物count++;W -= weight; // 更新剩余载重量} else {break;}}return count;
}int main() {vector<int> weights = {4, 8, 1, 5, 2}; // 货物重量int W;cout << "请输入船的最大载重量: ";cin >> W;cout << "最多可以装载 " << maxLoad(weights, W) << " 件货物。" << endl;return 0;
}