貪心算法（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;
}
- 分糖果問題
有若干孩子和糖果，每個孩子有一個貪婪因子（表示至少需要多少糖果才能滿足），每個糖果有一個大小。問最多能滿足多少孩子？
策略：
優先滿足需求最小的孩子：因為需求小的孩子更容易被滿足，這樣可以騰出更多較大的糖果來滿足其他孩子。
優先使用最小的糖果：因為較小的糖果可能無法滿足需求大的孩子，但可以滿足需求小的孩子。
#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;
}
- 最優裝載問題
有一艘船，載重量為 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;
}
