使用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))
网站名称:使用python实现一个贪心算法-创新互联
URL网址:http://myzitong.com/article/ddohhh.html