【CS.AL】算法核心之贪心算法：从入门到进阶

1000.1.CS.AL.1.4-核心-GreedyAlgorithm-Created: 2024-06-13.Thursday17:47

1. 概述

贪心算法是一种求解优化问题的算法策略。在每一步选择中，贪心算法都会选择当前最优解，希望通过一系列局部最优解的选择，达到全局最优解。贪心算法不回溯，不进行全局考虑，而是根据局部情况作出当前最优的选择。

2. 适用场景

贪心算法适用于一类特殊问题，即具有贪心选择性质的问题。这类问题满足每一步的选择都是局部最优的，并且不同步骤之间没有依赖关系，可以独立地做出选择。在这种情况下，贪心算法通常可以找到全局最优解或者近似最优解。

3. 设计步骤

1. 确定问题的最优解性质：贪心算法求解问题时，首先要确定问题是否具有最优子结构和贪心选择性质。如果满足这两个性质，那么贪心算法可能是可行的。
2. 选择合适的贪心策略：在每一步中，需要选择一个局部最优解。这就要根据问题的具体特点，设计适合的贪心策略，使得每次选择都是当前的最优解。
3. 构建贪心算法：根据选择的贪心策略，逐步构建出贪心算法，不断做出当前最优的选择，直至达到全局最优解或者满足问题的要求。

4. 优缺点

• 优点：贪心算法通常简单、高效，且易于实现。在一些特定问题中，贪心算法可以快速找到最优或近似最优解。
• 缺点：贪心算法并不适用于所有问题，有些问题并不具备贪心选择性质，因此贪心算法可能得到局部最优解而不是全局最优解。在这种情况下，需要考虑其他算法策略。

5. 典型应用

• 最小生成树问题：如Prim算法和Kruskal算法用于求解图中的最小生成树。
• 背包问题：如分数背包问题、0-1背包问题等，贪心算法在某些情况下可以得到近似最优解。
• 霍夫曼编码：用于数据压缩，通过贪心选择构建最优前缀编码。
• 最短路径问题：如Dijkstra算法和A*算法用于求解图中的最短路径。

6. 题目和代码示例

6.1 简单题目：找零问题

题目描述：给定不同面值的硬币，求最少硬币数使得总金额为给定值。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>// 函数声明
int coinChange(std::vector<int>& coins, int amount);int main() {std::vector<int> coins = {1, 2, 5};int amount = 11;std::cout << "最少硬币数: " << coinChange(coins, amount) << std::endl;return 0;
}// 找零问题：求最少硬币数
int coinChange(std::vector<int>& coins, int amount) {// 步骤 1: 对硬币面值从大到小排序std::sort(coins.rbegin(), coins.rend());int count = 0;// 步骤 2: 遍历硬币面值，逐步减少目标金额for (int coin : coins) {while (amount >= coin) {amount -= coin;count++;}}// 步骤 3: 检查是否正好找零成功return amount == 0 ? count : -1;
}

Ref. ![[1000.03.CS.PL.C++.4.2-STL-Algorithms-SortingOperations#1.1 简述]]

Others.

def coin_change(coins, amount):coins.sort(reverse=True)count = 0for coin in coins:while amount >= coin:amount -= coincount += 1return count if amount == 0 else -1# 示例
coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # 输出: 3 (5 + 5 + 1)

6.2 中等题目：区间调度问题

题目描述：给定多个会议的开始和结束时间，求最多能安排的会议数量。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>// 会议结构体
struct Meeting {int start;int end;
};// 函数声明
int maxMeetings(std::vector<Meeting>& meetings);int main() {std::vector<Meeting> meetings = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};std::cout << "最多能安排的会议数量: " << maxMeetings(meetings) << std::endl;return 0;
}// 区间调度问题：求最多能安排的会议数量
int maxMeetings(std::vector<Meeting>& meetings) {// 步骤 1: 根据会议结束时间排序std::sort(meetings.begin(), meetings.end(), [](const Meeting& a, const Meeting& b) {return a.end < b.end;});int count = 0;int endTime = 0;// 步骤 2: 遍历会议，选择结束时间最早的会议for (const auto& meeting : meetings) {if (meeting.start >= endTime) {count++;endTime = meeting.end;}}return count;
}

ref.

def max_meetings(meetings):meetings.sort(key=lambda x: x[1])count = 0end_time = 0for meeting in meetings:if meeting[0] >= end_time:count += 1end_time = meeting[1]return count# 示例
meetings = [(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)]
print(max_meetings(meetings))  # 输出: 4

6.3 困难题目：分数背包问题

题目描述：给定物品的重量和价值，求在背包容量限制下的最大价值，物品可以分割。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>// 物品结构体
struct Item {double value;double weight;
};// 函数声明
double fractionalKnapsack(std::vector<Item>& items, double capacity);int main() {std::vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};double capacity = 50;std::cout << "背包的最大价值: " << fractionalKnapsack(items, capacity) << std::endl;return 0;
}// 分数背包问题：求在背包容量限制下的最大价值
double fractionalKnapsack(std::vector<Item>& items, double capacity) {// 步骤 1: 根据物品单位重量价值排序std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {return (a.value / a.weight) > (b.value / b.weight);});double totalValue = 0;// 步骤 2: 遍历物品，选择单位重量价值最高的物品for (const auto& item : items) {if (capacity >= item.weight) {capacity -= item.weight;totalValue += item.value;} else {totalValue += item.value * (capacity / item.weight);break;}}return totalValue;
}

ref.

def fractional_knapsack(values, weights, capacity):items = list(zip(values, weights))items.sort(key=lambda x: x[0] / x[1], reverse=True)total_value = 0for value, weight in items:if capacity >= weight:capacity -= weighttotal_value += valueelse:total_value += value * (capacity / weight)breakreturn total_value# 示例
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(fractional_knapsack(values, weights, capacity))  # 输出: 240.0

7. 题目和思路表格

8. 总结

贪心算法是一种简单而高效的算法策略，在解决满足贪心选择性质的问题时，能够得到较好的结果。然而，要注意贪心算法的局限性，它不适用于所有问题，有些问题需要考虑其他算法设计策略，如分治、动态规划等。因此，在实际应用中，需要根据问题的性质和要求选择合适的算法策略。通过理解和掌握上述贪心算法的例子和思路，能够有效地提升解决问题的能力。

References