贪心算法：从局部最优到全局最优

贪心算法是一种在每一步选择中都采取当前情况下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。这种算法并不追求全局最优解，而是通过局部最优的选择来达到全局最优解。下面我们将通过一些实例和源码来理解贪心算法的基本原理和应用。
示例1：找零问题
假设我们有一个硬币面值为1、5和10，我们要找零，问最少需要多少个硬币？
贪心策略：优先使用大面值的硬币。
代码实现（Python）：

def make_change(money, coins):
coins.sort(reverse=True)  # 按面值从大到小排序
count = 0
for coin in coins:
while money >= coin:
money -= coin
count += 1
return count

示例2：最小生成树问题
给定一个带权重的图，如何找到连接所有节点的权重最小的树？这就是最小生成树问题。常见的算法有Prim算法和Kruskal算法。这里我们介绍Kruskal算法。
贪心策略：按照边的权重从小到大排序，优先选择权重最小的边，如果这条边不会与已选择的边形成环，则加入最小生成树。
代码实现（Python）：
```python
class Graph:
def init(self, vertices):
self.V = vertices
self.graph = [] # 存储边的列表，例如：[(0, 1, 10), (1, 2, 6), …]
self.parent = [-1] self.V # 记录每个顶点的父节点，用于检测环
self.rank = [0] self.V # 记录每个节点的秩，用于合并操作
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else: # 如果秩相同，合并后新节点的秩加1
parent[yroot] = xroot
rank[xroot] += 1
def kruskal(self):
edges = [] # 存储边的列表，按照权重从小到大排序
for u in range(self.V):
for v in range(u + 1, self.V): # 枚举每一条边 (u, v)
edges.append((self.graph[u][2], u, v)) # (权重, u节点索引, v节点索引)
edges.sort() # 按权重从小到大排序
res = 0 # 最小生成树的权值和
parent = [-1] * self.V # 初始化并查集数据结构，默认为每个节点独立为一个集合
for u in range(self.V): # 对每一条边进行判断是否加入最小生成树中
x, y = edges[u][1], edges[u][2] # (u节点索引, v节点索引) 代表边 (u, v) 的索引位置信息。取出对应的节点信息并加入到对应的集合中。并判断两个节点是否在同一个集合中。如果不在同一个集合中则说明该边加入到最小生成树中。将两个节点进行合并操作。最后统计最小生成树的权值和即可。 记录每条边的权值以及是否被加入到最小生成树中。如果被加入到最小生成树中则对应的变量加一。最后返回最小生成树的权值和即可。如果该边加入到最小生成树中则对应的最小生成树的权值