本文给大家分享怎样使用Python实现贪心算法，小编觉得比较有趣，因此分享给大家作参考，如果也对贪心算法比较好奇，那就继续往下看吧。
       超市有m个顾客要结账，每个顾客结账的时间为Ti（ i取值从1到m）。超市有n个结账出口，请问全部顾客怎么选择出口，可以最早完成全部顾客的结账，并用代码实现。
       其实利用的就是贪心算法来解决这个问题，那么，什么是贪心算法？怎么用贪心算法解决这个问题？让我一一道来。

       一、贪心算法简介

       贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。

       二、解决思路

       1.思路

       可以先让前N个人付款 后边顾客不断找出付款时间最短的依次排到前N个顾客按时间最长到最短的后边

       2.问题分解

       可以先假设只有一个收银台，那么我们可以很快的反应过来，最优的顺序就是按时间由小到大依次进行。即最优解为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进行举报，并提供相关证据，查实之后，将立刻删除涉嫌侵权内容。

猜你喜欢

• Python3数据类型包括哪些，作用和用法是什么

  Python 3 中有六个标准的数据类型：Numbers（数字）、String（字符串）、List（列表）、Tuple（元组）、Sets（集合）、Dictionaries（字典）。

• Python程序设计思想的核心是什么，有哪些基础知识

  本篇文章给大家带来了关于python的相关知识，其中主要整理了程序设计思想的相关问题，Python是一种面向对象oop(Object Oriented Programming)的脚本语言，编程思想的核心就是理解功能逻辑，下

• Pycharm远程连接服务器步骤操作是什么

  本文主要介绍了Pycharm远程连接服务器跑代码的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧

• Python学习过程中有什么常见的错误

  当初学 Python 时，想要弄懂 Python 的错误信息的含义可能有点复杂。这里列出了常见的的一些让你程序 crash 的运行时错误。1）忘记在...

• 基于Python如何实现动态鞭炮，要点是什么

  内容介绍1视频帧采样2将图片转为字符画2.1创建像素-字符索引2.2将图片逐像素转换为字符3将字符图像合成视频4完整代码5参考前言：放鞭炮贺新春，在我国有两千多年历史。关于鞭炮的起源，有