当前位置 博文首页 > 陈旻彦的博客:贪心算法python实现,python实现贪心算法案例
贪心算法的思想:
贪心算法是指:在每一步求解的步骤中,它要求“贪婪”的选择最佳操作,并希望通过一系列的最优选择,能够产生一个问题的(全局的)最优解。
贪心算法每一步必须满足一下条件:
1、可行的:即它必须满足问题的约束。
2、局部最优:他是当前步骤中所有可行选择中最佳的局部选择。
3、不可取消:即选择一旦做出,在算法的后面步骤就不可改变了。
贪心算法的经典例子:
活动选择问题,找零钱问题,摇摆问题,删数问题等。
以找零问题为例来阐述贪心算法的具体步骤:
问题描述:假设商店老板需要找零n元钱,钱币的面额有:100元、50元、20元、10元,5元、1元,如何找零使得所需钱币的数量最小?
解题思路:贪心选择:老板要找零99元的话,他有上面的面值分别为50,20,10,5,1元的钞票,为了找给我最少的硬币数,他首先考虑50元的,能找99/50=1张,然后看20元,能找49/20=2张,剩下9元,然后看10元,不能找,那么就考虑5元… 即每次考虑当前看起来最优的选择。
最优子结构:从初始状态出发,每步都经过贪心选择,最终得到问题的最优解。第一张50元是第一步找零局部最优,以此每步达到局部最优。寄希望于局部最优的选择能够导致全局最优解。
代码实现:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar? 6 14:37:15 2021
@author: iron
"""
#贪心算法例子
t = [100, 50, 20, 10, 5, 1]
def change(t, n):? # n指的总金额
m = [0 for _ in range(len(t))]? # 创建一个和t一样长但全是0的列表
# 这里假设t都是倒序排好的
for i, money in enumerate(t):
m[i] = n // money? # n整除money:376//100=3
n = n % money? # n对money取余:376%100=76
return m, n? # 如果到最后找不开,n就是找不开的钱
print(change(t, 376))? # ([3, 1, 1, 1, 1], 0)? 即:300+50+20+5+1
# 如果t = [100, 50, 20, 5],则有1块钱找不开,
print(change(t, 451))? # ([4, 1, 0, 0], 1)
结果展示:
当找零376元时:需要3张100元,1张50元,一张20元,一张5元,一张1元。
当找零451元时:需要4张100元,1张50元,一张1元。
cs