贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。以下是一些常见的贪心算法应用实例：
1. 钱币找零问题：
在找零时，希望用最少数量的钱币凑成特定的金额。贪心算法在此类问题中会选择当前面值最大的钱币，直到凑成所需金额。
（1）Python代码实现：
import matplotlib.pyplot as plt
from matplotlib.font_manager import FontProperties
# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei'] # 使用黑体
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号
def coin_change(coins, amount):
# 对钱币面值进行降序排序
coins.sort(reverse=True)
count = 0
result = []
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
result.append(coin)
return count, result
# 示例钱币面值和目标金额
coins = [25, 10, 5, 1] # 美元硬币面值（25美分、10美分、5美分、1美分）
amount = 63 # 目标金额（63美分）
# 调用函数
count, result = coin_change(coins, amount)
# 打印结果
print(f"最少需要 {count} 个硬币")
print(f"硬币组合: {result}")
# 绘制结果图
plt.figure(figsize=(10, 4))
plt.bar(range(len(result)), result, color='skyblue')
plt.xlabel('硬币编号')
plt.ylabel('硬币面值')
plt.title('硬币找零结果')
plt.xticks(range(len(result)), [f'硬币{i+1}' for i in range(len(result))])
plt.show()（2）函数定义：coin_change(coins, amount): 该函数接受一个硬币面值列表 coins 和一个目标金额 amount。对硬币面值进行降序排序，以便从最大面值开始选择。使用一个循环来选择尽可能多的最大面值硬币，直到金额不足为止。返回使用的硬币数量和具体的硬币组合。
（3）示例数据：coins = [25, 10, 5, 1]：表示可用的硬币面值。amount = 63：目标金额为63美分。
（4）结果绘制：使用 matplotlib 绘制一个条形图，展示每种硬币的面值。图中每个条形代表一个硬币，条形的高度表示硬币的面值。
2. 霍夫曼编码（Huffman Coding）：
在数据压缩中，贪心算法用于构建最小长度的前缀编码。霍夫曼编码是一种基于符号出现频率的贪心算法，它优先为出现频率高的符号分配较短的编码。
（1）Python代码实现：
import heapq
import matplotlib.pyplot as plt
from collections import defaultdict
# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei'] # 使用黑体
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号
class Node:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
# 用于优先队列的比较
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(char_freq):
# 创建一个优先队列
priority_queue = [Node(char, freq) for char, freq in char_freq.items()]
heapq.heapify(priority_queue)
while len(priority_queue) > 1:
# 取出两个频率最小的节点
left = heapq.heappop(priority_queue)
right = heapq.heappop(priority_queue)
# 创建一个新的内部节点
merged = Node(None, left.freq + right.freq)
merged.left = left
merged.right = right
# 将新节点重新插入优先队列
heapq.heappush(priority_queue, merged)
return priority_queue[0]
def assign_codes(node, prefix="", code_dict=None):
if code_dict is None:
code_dict = {}
if node is not None:
if node.char is not None:
code_dict[node.char] = prefix
assign_codes(node.left, prefix + "0", code_dict)
assign_codes(node.right, prefix + "1", code_dict)
return code_dict
def huffman_encoding(data):
# 统计字符频率
char_freq = defaultdict(int)
for char in data:
char_freq[char] += 1
# 构建霍夫曼树
huffman_tree = build_huffman_tree(char_freq)
# 分配编码
huffman_codes = assign_codes(huffman_tree)
# 编码数据
encoded_data = ''.join(huffman_codes[char] for char in data)
return encoded_data, huffman_codes
# 示例数据
data = "this is an example of a huffman tree"
# 进行霍夫曼编码
encoded_data, huffman_codes = huffman_encoding(data)
# 打印结果
print("霍夫曼编码结果:")
for char, code in huffman_codes.items():
print(f"{char}: {code}")
# 绘制结果图
plt.figure(figsize=(10, 6))
plt.bar(huffman_codes.keys(), [len(code) for code in huffman_codes.values()], color='skyblue')
plt.xlabel('字符')
plt.ylabel('编码长度')
plt.title('霍夫曼编码结果')
plt.show()（2）节点类：Node 类用于表示霍夫曼树的节点，包含字符、频率、左子节点和右子节点。__lt__ 方法用于优先队列的比较。
（3）构建霍夫曼树：build_huffman_tree 函数通过优先队列构建霍夫曼树。每次从队列中取出两个频率最小的节点，合并后重新插入队列，直到队列中只剩下一个节点。
（4）分配编码：assign_codes 函数递归地为霍夫曼树的每个节点分配编码。
（5）霍夫曼编码：huffman_encoding 函数统计字符频率，构建霍夫曼树，并为每个字符分配编码。最后，将数据编码为霍夫曼编码字符串。
（6）结果绘制：使用 matplotlib 绘制一个条形图，展示每个字符的编码长度。
3. 图的最小生成树：
如普里姆算法（Prim's algorithm）和克鲁斯卡尔算法（Kruskal's algorithm），用于在图的顶点之间找到最短的边集合，使得所有顶点都被连接起来。这些算法通过逐步添加最短或权重最小的边来构建最小生成树。
（1）Python代码实现：
import networkx as nx
import matplotlib.pyplot as plt
# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei'] # 使用黑体
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号
# 定义图的边和权重
edges = [
('A', 'B', 1),
('A', 'C', 4),
('B', 'C', 2),
('B', 'D', 5),
('C', 'D', 1),
('C', 'E', 3),
('D', 'E', 4),
('D', 'F', 2),
('E', 'F', 6),
('E', 'G', 3),
('F', 'G', 1)
]
# 创建图
G = nx.Graph()
G.add_weighted_edges_from(edges)
# 普里姆算法实现最小生成树
def prim_mst(G):
mst = nx.Graph()
start_node = list(G.nodes())[0]
mst.add_node(start_node)
while len(mst.nodes()) < len(G.nodes()):
edges = [(u, v, G[u][v]['weight']) for u in mst.nodes() for v in G.neighbors(u) if v not in mst.nodes()]
min_edge = min(edges, key=lambda x: x[2])
mst.add_edge(min_edge[0], min_edge[1], weight=min_edge[2])
return mst
# 克鲁斯卡尔算法实现最小生成树
def kruskal_mst(G):
mst = nx.Graph()
edges = sorted(G.edges(data=True), key=lambda x: x[2]['weight'])
for u, v, data in edges:
if u not in mst.nodes() or v not in mst.nodes() or not nx.is_connected(mst):
mst.add_edge(u, v, weight=data['weight'])
return mst
# 计算最小生成树
prim_mst_result = prim_mst(G)
kruskal_mst_result = kruskal_mst(G)
# 绘制原始图和最小生成树
plt.figure(figsize=(14, 6))
plt.subplot(1, 3, 1)
nx.draw(G, with_labels=True, node_color='lightblue', node_size=800, font_size=15, font_weight='bold', edge_color='gray')
plt.title('原始图')
plt.subplot(1, 3, 2)
nx.draw(prim_mst_result, with_labels=True, node_color='lightblue', node_size=800, font_size=15, font_weight='bold', edge_color='green')
plt.title('普里姆算法最小生成树')
plt.subplot(1, 3, 3)
nx.draw(kruskal_mst_result, with_labels=True, node_color='lightblue', node_size=800, font_size=15, font_weight='bold', edge_color='red')
plt.title('克鲁斯卡尔算法最小生成树')
plt.tight_layout()
plt.show()（2）图的定义：使用 networkx 库创建一个无向图，并添加带权重的边。
（3）普里姆算法：prim_mst 函数从图中的一个起始节点开始，逐步添加连接到当前最小生成树的最短边，直到所有节点都被连接。
（4）克鲁斯卡尔算法：kruskal_mst 函数对所有边按权重进行排序，然后按顺序添加边，确保每次添加后图仍然是无环的，直到所有节点都被连接。
（5）结果绘制：使用 matplotlib 和 networkx 绘制原始图和两种算法得到的最小生成树。原始图的边用灰色表示，普里姆算法的结果用绿色表示，克鲁斯卡尔算法的结果用红色表示。
4. 单源最短路径问题：
如迪杰斯特拉算法（Dijkstra's algorithm）和贝尔曼-福特算法（Bellman-Ford algorithm），用于找到从单个源点到所有其他顶点的最短路径。这些算法通过逐步更新最短路径估计值来找到全局最短路径。
（1）Python代码实现：
import networkx as nx
import matplotlib.pyplot as plt
import heapq
# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei'] # 使用黑体
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号
# 定义图的边和权重
edges = [
('A', 'B', 1),
('A', 'C', 4),
('B', 'C', 2),
('B', 'D', 5),
('C', 'D', 1),
('C', 'E', 3),
('D', 'E', 4),
('D', 'F', 2),
('E', 'F', 6),
('E', 'G', 3),
('F', 'G', 1)
]
# 创建图
G = nx.Graph()
G.add_weighted_edges_from(edges)
# 迪杰斯特拉算法实现单源最短路径
def dijkstra(G, source):
distances = {node: float('inf') for node in G.nodes()}
distances[source] = 0
priority_queue = [(0, source)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in G[current_node].items():
distance = current_distance + weight['weight']
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# 贝尔曼-福特算法实现单源最短路径
def bellman_ford(G, source):
distances = {node: float('inf') for node in G.nodes()}
distances[source] = 0
for _ in range(len(G.nodes()) - 1):
for u, v, weight in G.edges(data='weight'):
if distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
return distances
# 计算单源最短路径
source = 'A'
dijkstra_distances = dijkstra(G, source)
bellman_ford_distances = bellman_ford(G, source)
# 绘制原始图和最短路径结果
plt.figure(figsize=(14, 6))
plt.subplot(1, 2, 1)
nx.draw(G, with_labels=True, node_color='lightblue', node_size=800, font_size=15, font_weight='bold', edge_color='gray')
plt.title('原始图')
plt.subplot(1, 2, 2)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=800, font_size=15, font_weight='bold', edge_color='gray')
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
# 绘制迪杰斯特拉算法的最短路径
for node in dijkstra_distances:
if node != source:
path = nx.shortest_path(G, source, node, weight='weight')
nx.draw_networkx_edges(G, pos, edgelist=[(path[i], path[i+1]) for i in range(len(path)-1)], width=2, edge_color='green', alpha=0.7)
plt.title('迪杰斯特拉算法最短路径')
plt.show()（2）图的定义：使用 networkx 库创建一个无向图，并添加带权重的边。
（3）迪杰斯特拉算法：dijkstra 函数使用优先队列来逐步更新最短路径估计值，直到找到从源点到所有其他顶点的最短路径。
（4）贝尔曼-福特算法：bellman_ford 函数通过多次遍历图中的所有边来更新最短路径估计值，适用于包含负权重边的图。
（5）结果绘制：使用 matplotlib 和 networkx 绘制原始图和迪杰斯特拉算法得到的最短路径。原始图的边用灰色表示，最短路径用绿色表示。
5. 分数背包问题：
在此类问题中，希望最大化价值的总和，同时不超过一个给定的重量限制。贪心算法会选择单位重量价值最高的物品，直到达到重量限制。
（1）Python代码实现：
import matplotlib.pyplot as plt
# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei'] # 使用黑体
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号
# 物品的重量和价值
items = [
{'weight': 10, 'value': 60},
{'weight': 20, 'value': 100},
{'weight': 30, 'value': 120}
]
# 背包的容量
capacity = 50
# 计算单位重量价值
def calculate_value_density(items):
for item in items:
item['value_density'] = item['value'] / item['weight']
return items
# 贪心算法解决分数背包问题
def fractional_knapsack(items, capacity):
items = calculate_value_density(items)
items.sort(key=lambda x: x['value_density'], reverse=True)
total_value = 0
total_weight = 0
result = []
for item in items:
if total_weight + item['weight'] <= capacity:
total_weight += item['weight']
total_value += item['value']
result.append({'item': item, 'fraction': 1})
else:
remaining_capacity = capacity - total_weight
fraction = remaining_capacity / item['weight']
total_value += item['value'] * fraction
result.append({'item': item, 'fraction': fraction})
break
return total_value, result
# 解决问题
total_value, result = fractional_knapsack(items, capacity)
# 打印结果
print(f"最大总价值: {total_value}")
for item in result:
print(f"物品: {item['item']}, 分割比例: {item['fraction']}")
# 绘制结果图
weights = [item['item']['weight'] * item['fraction'] for item in result]
values = [item['item']['value'] * item['fraction'] for item in result]
plt.figure(figsize=(10, 6))
plt.bar(range(len(result)), weights, color='skyblue')
plt.xlabel('物品')
plt.ylabel('重量')
plt.title('分数背包问题结果')
plt.xticks(range(len(result)), [f'物品{i+1}' for i in range(len(result))])
plt.show()（2）物品定义：items 列表包含每个物品的重量和价值。
（3）计算单位重量价值：calculate_value_density 函数计算每个物品的单位重量价值（价值密度）。
（4）贪心算法：fractional_knapsack 函数按单位重量价值对物品进行降序排序，然后依次选择物品，直到达到背包容量限制。如果物品不能完全放入背包，则选择该物品的一部分。
（5）结果绘制：使用 matplotlib 绘制一个条形图，展示每个物品在背包中的重量。图中每个条形的高度表示该物品在背包中的实际重量。
6. 任务调度问题：
选择最短的作业优先执行，以减少等待时间。这类问题中，贪心算法会优先安排执行时间最短的作业，以提高整体效率。
（1）Python代码实现：
import matplotlib.pyplot as plt
# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei'] # 使用黑体
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号
# 作业列表，包含作业名称和执行时间
jobs = [
{'name': 'Job A', 'duration': 6},
{'name': 'Job B', 'duration': 8},
{'name': 'Job C', 'duration': 7},
{'name': 'Job D', 'duration': 5},
{'name': 'Job E', 'duration': 3}
]
# 最短作业优先算法
def shortest_job_first(jobs):
# 按执行时间升序排序
jobs.sort(key=lambda x: x['duration'])
scheduled_jobs = []
current_time = 0
for job in jobs:
job['start_time'] = current_time
job['end_time'] = current_time + job['duration']
scheduled_jobs.append(job)
current_time += job['duration']
return scheduled_jobs
# 执行SJF算法
scheduled_jobs = shortest_job_first(jobs)
# 打印结果
print("作业调度结果:")
for job in scheduled_jobs:
print(f"{job['name']}: 开始时间 = {job['start_time']}, 结束时间 = {job['end_time']}")
# 绘制结果图
plt.figure(figsize=(10, 6))
for i, job in enumerate(scheduled_jobs):
plt.barh(i, job['end_time'] - job['start_time'], left=job['start_time'], color='skyblue')
plt.text(job['start_time'] + job['duration'] / 2, i, job['name'], ha='center', va='center', color='black')
plt.yticks(range(len(scheduled_jobs)), [job['name'] for job in scheduled_jobs])
plt.xlabel('时间')
plt.title('最短作业优先调度结果')
plt.grid(True)
plt.show()（2）作业定义：jobs 列表包含每个作业的名称和执行时间。
（3）最短作业优先算法：shortest_job_first 函数按执行时间对作业进行升序排序，然后依次安排作业的开始和结束时间。
（4）结果绘制：使用 matplotlib 绘制一个水平条形图，展示每个作业的执行时间。图中每个条形的高度表示作业的执行时间，条形的位置表示作业的开始时间。
7. 区间调度问题（活动选择问题）：
在给定一系列有重叠区间的活动中，选择尽可能多的两两不相交的活动。贪心算法会按照活动的结束时间或开始时间进行排序，并依次选择活动，以确保选择的活动数量最多。
（1）Python代码实现：
import matplotlib.pyplot as plt
# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei'] # 使用黑体
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号
# 活动列表，包含活动的开始时间和结束时间
activities = [
{'name': 'Activity A', 'start': 1, 'end': 4},
{'name': 'Activity B', 'start': 3, 'end': 5},
{'name': 'Activity C', 'start': 0, 'end': 6},
{'name': 'Activity D', 'start': 5, 'end': 7},
{'name': 'Activity E', 'start': 8, 'end': 9},
{'name': 'Activity F', 'start': 5, 'end': 9},
{'name': 'Activity G', 'start': 6, 'end': 10},
{'name': 'Activity H', 'start': 8, 'end': 11} # 修正了键名
]
# 贪心算法解决区间调度问题
def greedy_activity_selector(activities):
# 按结束时间升序排序
activities.sort(key=lambda x: x['end'])
selected_activities = [activities[0]]
for activity in activities[1:]:
if activity['start'] >= selected_activities[-1]['end']:
selected_activities.append(activity)
return selected_activities
# 执行贪心算法
selected_activities = greedy_activity_selector(activities)
# 打印结果
print("选择的活动:")
for activity in selected_activities:
print(f"{activity['name']}: 开始时间 = {activity['start']}, 结束时间 = {activity['end']}")
# 绘制结果图
plt.figure(figsize=(10, 6))
for i, activity in enumerate(activities):
plt.barh(i, activity['end'] - activity['start'], left=activity['start'], color='gray')
plt.text(activity['start'] + (activity['end'] - activity['start']) / 2, i, activity['name'], ha='center', va='center', color='black')
for i, activity in enumerate(selected_activities):
plt.barh(i, activity['end'] - activity['start'], left=activity['start'], color='skyblue')
plt.text(activity['start'] + (activity['end'] - activity['start']) / 2, i, activity['name'], ha='center', va='center', color='black')
plt.yticks(range(len(activities)), [activity['name'] for activity in activities])
plt.xlabel('时间')
plt.title('区间调度问题结果')
plt.grid(True)
plt.show()（2）活动定义：activities 列表包含每个活动的名称、开始时间和结束时间。
（3）贪心算法：greedy_activity_selector 函数按活动的结束时间进行升序排序，然后依次选择活动。选择的条件是当前活动的开始时间不早于上一个选择活动的结束时间。
（4）结果绘制：使用 matplotlib 绘制一个水平条形图，展示所有活动的时间区间。选择的活动用浅蓝色表示，未选择的活动用灰色表示。图中每个条形的高度表示活动的持续时间，条形的位置表示活动的开始时间。
此外，还有一些其他类型的贪心算法应用，如近似贪心算法、参数化贪心算法等。这些算法在特定问题中可能具有不同的表现和应用方式。
需要注意的是，贪心算法并不总是能得到最优解，但在某些情况下，它提供了一种快速且有效的解决方案。因此，在选择使用贪心算法时，需要仔细分析问题的性质，并验证算法的正确性和有效性。
标签：node,plt,weight,七种,start,算法,实例,activity,贪心 From： https://blog.csdn.net/lzm12278828/article/details/144974645