本文主要是介绍【CS.AL】算法核心之贪心算法:从入门到进阶,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 1. 概述
- 2. 适用场景
- 3. 设计步骤
- 4. 优缺点
- 5. 典型应用
- 6. 题目和代码示例
- 6.1 简单题目:找零问题
- 6.2 中等题目:区间调度问题
- 6.3 困难题目:分数背包问题
- 7. 题目和思路表格
- 8. 总结
- References
1000.1.CS.AL.1.4-核心-GreedyAlgorithm-Created: 2024-06-13.Thursday17:47
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. 题目和思路表格
序号 | 题目 | 题目描述 | 贪心策略 | 代码实现 |
---|---|---|---|---|
1 | 找零问题 | 求最少硬币数使得总金额为给定值 | 每次选择面值最大的硬币 | 代码 |
2 | 区间调度问题 | 求最多能安排的会议数量 | 每次选择结束时间最早的会议 | 代码 |
3 | 分数背包问题 | 求在背包容量限制下的最大价值 | 每次选择单位重量价值最高的物品 | 代码 |
4 | 最小生成树 | 用于求解图中的最小生成树 | 每次选择权重最小的边 | - |
5 | 霍夫曼编码 | 用于数据压缩 | 每次选择频率最低的节点进行合并 | - |
6 | 最短路径 | 用于求解图中的最短路径 | 每次选择当前节点到未访问节点的最短路径 | - |
7 | 活动选择问题 | 求最多可选择的互不相交的活动 | 每次选择结束时间最早的活动 | - |
8 | 跳跃游戏 | 判断能否跳到最后一个位置 | 每次选择跳跃距离最大的步骤 | - |
9 | 加油站问题 | 求最少加油次数到达目的地 | 每次选择油量最多的加油站 | - |
10 | 股票买卖 | 求最大收益 | 每次选择局部最低点买入,局部最高点卖出 | - |
8. 总结
贪心算法是一种简单而高效的算法策略,在解决满足贪心选择性质的问题时,能够得到较好的结果。然而,要注意贪心算法的局限性,它不适用于所有问题,有些问题需要考虑其他算法设计策略,如分治、动态规划等。因此,在实际应用中,需要根据问题的性质和要求选择合适的算法策略。通过理解和掌握上述贪心算法的例子和思路,能够有效地提升解决问题的能力。
References
这篇关于【CS.AL】算法核心之贪心算法:从入门到进阶的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!