Python怎样实现贪心算法?五点带你看懂贪心算法
Admin 2021-05-21 群英技术资讯 741 次浏览
本文给大家分享怎样使用Python实现贪心算法,小编觉得比较有趣,因此分享给大家作参考,如果也对贪心算法比较好奇,那就继续往下看吧。
超市有m个顾客要结账,每个顾客结账的时间为Ti( i取值从1到m)。超市有n个结账出口,请问全部顾客怎么选择出口,可以最早完成全部顾客的结账,并用代码实现。
其实利用的就是贪心算法来解决这个问题,那么,什么是贪心算法?怎么用贪心算法解决这个问题?让我一一道来。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择,就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪心算法不要回溯 。
可以先让前N个人付款 后边顾客不断找出付款时间最短的依次排到前N个顾客按时间最长到最短的后边
可以先假设只有一个收银台,那么我们可以很快的反应过来,最优的顺序就是按时间由小到大依次进行。即最优解为A={t(1),t(2),….t(n)}(其中t(i)为第i个用户需要的服务时间),则每个用户等待时间为:
T(1)=t(1);T(2)=t(1)+t(2);…T(n):t(1)+t(2)+t(3)+……t(n);
那么总等待时问,即最优值为:
TA=n*t(1)+(n-1)*t(2)+…+(n+1-j)t(i)+…2t(n-1)+t(n);
有了上边的分解,那么实现算法代码就非常的轻而易举了`
def greedy(customer_list, n): # customer_time_list为第j个队列上的某一个顾客的等待时间 # sum_customer_time_list是求和数组 # sum_customer_time_list[j]的值为第j个队列上所有顾客的等待时间 # min_sum_customer_time为结账最小时间 # 初始化一个大小为n的0列表 customer_time_list = [] sum_customer_time_list = [] num = 0 while num < n: customer_time_list.append(0) sum_customer_time_list.append(0) num += 1 min_sum_customer_time = 0 # 顾客的数量 m = len(customer_list) customer_list.sort() #列表升序排序 i = 0 j = 0 while i < m: customer_time_list[j] += customer_list[i] sum_customer_time_list[j] += customer_time_list[j] i += 1 j += 1 # 如果j到了最后一个结账出口,重新归零 if j == n: j = 0 # 汇总最小总时间 k = 0 while k < n: min_sum_customer_time += sum_customer_time_list[k] k += 1 return min_sum_customer_time
准备一个顾客排队序列和指定收银台数量,得到最小时间
customer_list = [6, 5, 3, 4, 2, 1] print(greedy(customer_list, 2))
程序主要是花费在对各顾客所需服务时间的排序和贪心算法,即计算平均服务时间上面。其中,贪心算法部分只有一重循环影响时间复杂度,其时间复杂度为O(n):而排序算法的时间复杂度为O(nlogn)。因此,综合来看算法的时间复杂度为O(nlogn)。
以上就是关于Python实现贪心算法的介绍了,现在大家对于贪心算法应该也有所了解了,希望大家阅读完这篇文章能有所收获,更多Python实现贪心算法内容,可以关注其他文章。
文本转载自脚本之家
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:mmqy2019@163.com进行举报,并提供相关证据,查实之后,将立刻删除涉嫌侵权内容。
猜你喜欢
这篇文章主要介绍了python可视化分析绘制带趋势线的散点图和边缘直方图,文章围绕主题展开详细的内容介绍,具有一定的参考价值,需要的小伙伴可以参考一下
这篇文章主要为大家介绍了用来将对象持久化的python pickle模块的用例详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
这篇文章给大家详细的介绍了python中set集合的使用,具有一定的借鉴和学习价值,感兴趣的朋友可以参考一下,希望大家阅读完这篇文章能有所收获,下面我们一起来学习一下吧。
这篇文章介绍了Python找水仙花数从分析到实现的过程,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
这篇文章主要介绍了Python全面解读高级特性切片,切片(slice)就是一种截取索引片段的技术,借助切片技术,我们可以十分灵活地处理序列类型的对象,下面我们一起进入文章了解更详细内容吧
成为群英会员,开启智能安全云计算之旅
立即注册Copyright © QY Network Company Ltd. All Rights Reserved. 2003-2020 群英 版权所有
增值电信经营许可证 : B1.B2-20140078 粤ICP备09006778号 域名注册商资质 粤 D3.1-20240008