Python实现贪心算法的示例

  • 更新时间:2022-09-07 08:44:07
  • 编辑:边浩初

今天一个研究生同学问我一个问题,问题如下:
超市有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实现贪心算法的资料请关注码农之家其它相关文章!

相关教程

  • python实现kMeans算法的详解

    给大家整理一篇关于python的教程,聚类是一种无监督的学习,将相似的对象放到同一簇中,有点像是全自动分类,簇内的对象越相似,簇间的对象差别越大,则聚类效果越好。本文主要为大家详细介绍了python实现kMeans算法,具有

    发布时间:2022-07-11

  • 实例详解Python实现数据结构线性链表(单链表)算法

    这篇文章主要介绍了Python实现数据结构线性链表(单链表)算法,结合实例形式分析了Python单链表的定义、节点插入、删除、打印等相关操作技巧,需要的朋友可以参考下

    发布时间:2020-01-27

  • 总结python3实现二叉树的遍历及递归算法

    这篇文章主要介绍了python3实现二叉树的遍历与递归算法解析(小结),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习

    发布时间:2020-03-13

  • Python实现插入排序算法示例效果

    这篇文章主要介绍了Python实现的直接插入排序算法,结合实例形式分析了Python直接插入排序算法的定义与使用相关操作技巧,代码备有较为详尽的注释便于理解,需要的朋友可以参考下

    发布时间:2020-01-27

  • 总结python八大排序算法速度示例比较

    这篇文章主要介绍了Python八大排序算法速度实例对比,具有一定参考价值,需要的朋友可以参考下。

    发布时间:2020-01-14

  • 对python数据切割归并算法的实例讲解

    今天小编就为大家分享一篇对python数据切割归并算法的实例讲解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧

    发布时间:2021-04-13

  • Python数据结构与算法中的队列详解(1)

    这篇文章主要为大家详细介绍了Python的队列,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下,希望能够给你带来帮助

    发布时间:2022-04-12

用户留言