已发布·持续改进
Algorithm
贪心算法在每一步都做出当前看来最好的选择且不回头，能快速解决区间调度、哈夫曼编码和分数背包等问题。
贪心算法把问题拆成一系列选择，在每一步按照固定的规则选出当前看起来最好的候选，并且不再修改这个决定。大多数贪心算法先对候选排序或放入优先队列，再逐个取出决定是否接受，因此代码简短，时间复杂度通常由排序或堆操作决定，为 O(n log n)。
贪心算法在适用的问题上是最快、最简单的解法，但并非总是正确。要保证得到最优解，必须同时满足贪心选择性质和最优子结构，通常用交换论证来证明。只要存在一个反例，例如用面值 1、3、4 的硬币凑出 6，就说明需要改用动态规划。哈夫曼编码、Dijkstra 最短路径和最小生成树等广泛使用的核心算法中也包含贪心思想。
学习时建议从区间调度（活动选择）入手，尝试用交换论证解释为什么“选择最早结束的活动”是正确的。接着动手实现哈夫曼编码、分数背包和用堆完成的会议室分配，并养成在小规模输入上与暴力搜索对比结果的习惯，这样在算法面试和刷题时就能迅速发现错误的贪心策略。
必须存在一个包含第一次贪心选择的最优解，这是贪心算法正确的核心条件。
证明把任意最优解逐个元素替换为贪心解中的元素不会变差，从而说明贪心规则是正确的。
按结束时间、单位重量价值或频率给候选排序，或从堆中取出，因此大多在 O(n log n) 内完成。
对任意硬币体系的找零或 0/1 背包，贪心规则会出错，此时应改用动态规划。
这个程序选出数量最多且互不重叠的会议。它先按结束时间对会议排序，只有当会议在上一次选中的会议结束之后开始时才接受。排序耗时 O(n log n)，扫描耗时 O(n)；示例从 11 个会议中选出 4 个。
greedy.py
def select_intervals(intervals):
"""Return a maximum set of non-overlapping half-open intervals [start, end)."""
chosen = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]): # earliest end first
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(select_intervals(meetings)) # [(1, 4), (5, 7), (8, 11), (12, 16)]
python greedy.py共六章，带你从安装一步步了解 贪心算法 的核心概念。
在这里提问、分享经验，交流关于 贪心算法 的看法。
还没有讨论。来发起第一个吧。
0 条评论
登录 · 登录后即可发表评论。
来发表第一条评论吧。