Python 贪心算法核心原理与实战案例解析
本文深入解析 Python 中贪心算法的实现逻辑，阐述其通过局部最优解逼近全局解的核心思想。文章包含硬币找零与任务规划两个经典案例，详细演示如何设计无后效性的贪心策略，并提供完整的 Python 代码实现与排序逻辑分析，帮助开发者掌握该算法在资源分配场景下的应用。
贪心算法概述
贪心算法
贪心算法（亦称贪婪算法）是一种在求解问题时，始终选取当前状态下最优或最有利选择的策略。它不追求从整体角度进行全局最优的考量，而是致力于在每一步中获取某种意义上的局部最优解。
需要注意的是，贪心算法并非适用于所有问题，其能否得到整体最优解取决于贪心策略的选择。所选用的策略必须具备无后效性，即过去的决策过程不会影响未来的状态，当前状态仅由当前决策决定。
基本思路与思想
基本思路
思想
贪心算法的基本执行流程是从问题的初始解开始，逐步推进。依据特定的优化测度，确保每一步都能获得局部最优解。每次仅考虑一个数据项，其选取需满足局部优化条件。若将下一个数据加入部分解会导致不可行，则跳过该数据，继续枚举，直到所有数据遍历完毕或无法再添加新元素为止。
算法执行步骤
步骤
- 遍历初始集合 X 中的所有备选元素。
- 依据贪心策略从集合 X 中选定一个元素，并将其加入可行解集合 S。
- 最终得到可行解 S。
其中 P 代表贪心策略，用于筛选符合特定条件的元素。
案例一：硬币找零问题
例子——硬币找零
假设某国流通的硬币面额包括 1、5、10、25 和 100 元五种。若店员需为顾客找零 a=36 元，目标是使使用的硬币数量最少。
在此场景下的贪心策略为：
首先找到最接近剩余金额 a 的最大面额，更新剩余金额 a，随后进入循环处理。
代码实现
def shortNum(a):
coins = [1,5,10,25,100]
out = []
coins = coins[::-1]
for i in coins:
num = a//i
out=out+[i,]*num
a = a-num*i
if a<=0:
break
return out
a = 36
print(shortNum(a))案例二：任务调度规划
例子——任务规划
问题描述：
输入为一组任务集合 X= [r1,r2,r3,...,rn]，每个任务 ri 均对应一个起始时间 ai 与结束时间 bi。
输出要求为找出数量最多的相容任务集合。
如上图所示，r1 与 r2 时间不重叠，即为相容；而 r3 与 r1 及 r2 的时间均存在重叠，故不相容。
针对此问题的贪心策略可设定为：
- 首先将结束时间最短的任务加入集合 S。
- 随后从剩余任务中选择结束时间最短的任务，并判断其与集合 S 中已有任务是否相容。
- 若发现不相容，则跳过该任务，选择下一个结束时间最短的任务进行比较。
- 重复上述循环，直至集合 X 为空。
代码实现
# 任务规划
from collections import OrderedDict
task = OrderedDict()
task['r1'] = [0,4]
task['r2'] = [5,8]
task['r3'] = [10,13]
task['r4'] = [15,18]
task['r5'] = [7,11]
task['r6'] = [2,6]
task['r7'] = [2,6]
task['r8'] = [2,6]
task['r9'] = [12,16]
task['r10'] = [12,16]
task['r11'] = [12,16]
task['r12'] = [0,3]
listTask = list(task.items())
# 根据bi进行排序，结束时间早的在前面（冒泡排序）
for i in range(len(listTask)-1):
for j in range(len(listTask)-i-1):
if listTask[j][1][1] > listTask[j+1][1][1]:
listTask[j],listTask[j+1]=listTask[j+1],listTask[j]
print(listTask)
out = []
out.append(listTask.pop(0))
def isValid(temp,out):
for k in range(len(out)):
if temp[1][0]<out[k][1][1]:
# 相交
return False
return True
for j in range(len(listTask)):
temp = listTask.pop(0)
# 判断是否相交
# 相交则continue
# 不相交则out.append(temp)
for k in range(len(out)):
if isValid(temp,out):
out.append(temp)
# else:continue 语句可以不写
else:
continue
print(out)以上即为 Python 贪心算法实现的详细内容，更多关于 Python 贪心算法的资料请关注本站其它相关文章！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
