4.1 贪心算法的定义。
贪心算法 (Greedy Algorithms) 是一类 算法，通过在每一步选择局部最优解来构建解决方案。每个步骤的选择都是基于当前状态的， 且不会在以后重新考虑。
贪心算法经常用于解决优化问题，就是为了最大化或最小化某个值。
贪心算法的基本原则
- 贪心选择: 在每一步，算法选择一个看起来是 最优的局部选择，期望能得到全局最优解。
- 最优子结构: 问题必须具有这样的属性， 即局部最优解可以结合成全局最优解。
- 单调性: 选择了某个局部最优步骤后， 后续选择不应该降低已有的解的质量。
贪心算法的优缺点
优点：
- 实现简单: 贪心算法一般容易理解和实现。
- 高效: 通常它们比更复杂的算法（例如动态规划）运行速度更快。
缺点：
- 缺乏全局最优性: 贪心算法不总能得到全局最优解。
- 并非所有问题都适用: 只有某些特定问题可以通过贪心算法解决。
有一类问题最好的解决方案就是用贪心算法。了解这些会对你有帮助。
4.2 找零问题。
问题:
我们有不同面值的硬币。需要找到用于找零的最小数量的硬币。
解决方案:
总是选择不超过剩余金额的最大面值的硬币。
时间复杂度: O(n), 其中 n 是硬币的种类数。
Python示例代码:
def min_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
4.3 背包问题
问题:
我们有已知价值和重量的物品。我们想在一个固定大小的背包里装入价值尽可能大的物品。
在这个问题中 物品可以被分割。例如，如果我们要买不同种类的谷物，可以选 1000 克或者 512 克。
解决方案:
按单位价值（价值/重量）对物品排序，然后选择单位价值最大的物品，直到装满背包。
时间复杂度: O(n log n), 其中 n 是物品的数量。
Python示例代码:
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, capacity):
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0
for item in items:
if capacity >= item.weight:
total_value += item.value
capacity -= item.weight
else:
total_value += item.ratio * capacity
break
return total_value
4.4 线段覆盖问题
问题:
在一条直线上有一些线段，由它们的端点 (x1, x2) 指定，还有一个目标线段。需要找到覆盖目标线段所有点的最小数量的线段。
解决方案:
根据右端点对线段进行排序，选择覆盖当前点的最小线段。
时间复杂度: O(n log n), 其中 n 是线段的数量。
Python示例代码:
def min_segments(segments):
segments.sort(key=lambda x: x[1])
count = 0
end = -float('inf')
for seg in segments:
if seg[0] > end:
end = seg[1]
count += 1
return count
GO TO FULL VERSION