算法设计与分析（第二章 贪心算法作业1-必做头歌

贪心算法第二章必做题目分析与设计
贪心算法是一种通过一系列局部最优选择来达到全局最优解的策略。它通常用于解决优化问题，在某些特定条件下能够提供高效的解决方案[^3]。以下是关于贪心算法第二章可能涉及的一些典型作业题及其分析。
1. 活动选择问题
这是一个典型的贪心算法应用案例，目标是从一组活动中选出最大数量的互不冲突的活动集合。假设每项活动都有一个开始时间和结束时间，则可以通过按结束时间排序并依次选取最早结束且与已选活动无冲突的活动来解决问题[^4]。
def activity_selection(activities):
activities.sort(key=lambda x: x[1]) # 按照结束时间排序
selected = []
last_end_time = float('-inf')

for start, end in activities:
if start >= last_end_time:
selected.append((start, end))
last_end_time = end

return selected
登录后复制
此代码实现了基于贪心原则的活动选择方法。
2. 区间覆盖问题
给定一条线段以及若干条较短的小线段，如何用最少的数量完全覆盖这条长线？可以将所有小线段按照右端点升序排列，然后从左至右扫描整个区域，每次都尝试找到能延伸最远距离的一段作为候选者加入最终方案中去[^5]。
3. 硬币找零问题
假设有几种不同面值的钱币无限供应量，问怎样凑成指定金额所需的总枚数最少? 这里需要注意的是并非所有的货币体系都适合采用简单的贪婪法则；只有当存在某种特殊关系时才可以直接运用这种方法得出正确结论。
def coin_change(coins, amount):
coins.sort(reverse=True)
count = 0

for coin in coins:
if amount == 0:
break

num_coins = amount // coin
count += num_coins
amount -= num_coins * coin

return count if amount == 0 else -1
登录后复制
上述函数展示了利用贪心思路解决硬币兑换难题的过程。
4. 装载问题
考虑一艘船的最大载重量W及N件物品各自的重量wi(i=1,...n)，试确定能否把这些货物全部装入船上而不超重。如果允许拆分单个物体的话则可转化为分数背包形式处理; 否则需借助其他更复杂的手段比如回溯法或者分支限界法等进一步探讨最佳组合方式。