今天一个研究生同学问我一个问题,问题如下:
超市有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实现贪心算法的示例的更多相关文章

  1. Python实现量子态采样

    量子态是用于表征一个量子系统所处状态的物理量,在矩阵力学中我们可以将其视为一个普通的矢量,在概率学上我们又可以将其转换为概率分布函数。在获得一个概率分布函数之后,我们自然可以对其进行采样,这就完成了对一个量子系统进行模拟采样的过程。什么是量子态矢量?在前面一篇量子系统模拟的博客中,我们介绍了使用py......

  2. python画图时设置分辨率和画布大小的实现(plt.figure())

    本文介绍了python画图时设置分辨率和画布大小的实现,主要使用plt.figure(),下面就一起来了解一下plt.figure()示例:?12345678910111213import numpy as npimport pandas as pdimport warningswarnings.f......

  3. pandas 颠倒列顺序的两种解决方案

    在数据预处理过程中可能需要将列的顺序颠倒,有两种方法。import numpy as npimport pandas as pddf = pd.DataFrame(np.array(range(20)).reshape(4,5))print(df)原始dataframe如下:0 1 2 3 ......

  4. Python抓取淘宝IP地址数据

    def fetch(ip):url = 'http://ip.taobao.com/service/getIpInfo.php?ip=' + ipresult = []try:response = urllib.urlopen(url).read()jsondata = json.loads(res......

  5. python shell 根据 ip 获取 hostname

    python shell 根据 ip 获取 hostname 或根据 hostname 获取 ip前言笔者有时候需要根据hostname获取ip 比如根据machine.company.com 获得ip 10.173.14.117本文地址 http://blog.csdn.net/never_cxb......

  6. 基于Python的接口自动化-读写配置文件

    引言在编写接口自动化测试脚本时,有时我们需要在代码中定义变量并给变量固定的赋值。为了统一管理和操作这些固定的变量,咱们一般会将这些固定的变量以一定规则配置到指定的配置文件中,后续需要用到这些变量和变量值时通过代码读取或者写入数据到该配置文件即可,使用配置文件的好处就是不用在程序员写死,可以使程序更灵......

  7. 用python批量移动文件

    我是用来移动图片的,其他格式的文档也是可以的,改下后缀列表就可以了import os,shutilimport datetime #将文件夹里的图片全部移动到新文件夹中#revised by Stephen Shen 2020-3-10 09:28:50 def renameFile(dst......

  8. Python基础(上篇)

    本篇文章主要内容:变量、注释、运算符、关键字、数据类型。本篇文章主要内容:变量、注释、运算符、关键字、数据类型。在入手变量之前我们先来看看经典的编程语句 → hello world 在python3中输出到控制台的函数是print()print("hello world") 一、......

  9. python pyppeteer 破解京东滑块功能的代码

    Pyppeteer简介介绍Pyppeteer之前先说一下Puppeteer,Puppeteer是谷歌出品的一款基于Node.js开发的一款工具,主要是用来操纵Chrome浏览器的 API,通过Javascript代码来操纵Chrome浏览器,完成数据爬取、Web程序自动测试等任务。在上篇文章给大家详......

  10. pytest进阶教程之fixture函数详解

    fixture函数存在意义与python自带的unitest测试框架中的setup、teardown类似,pytest提供了fixture函数用以在测试执行前和执行后进行必要的准备和清理工作。但是相对来说又比setup、teardown好用。firture相对于setup和teardown的优势命名......

随机推荐

  1. Java并发包源码学习系列:阻塞队列实现之LinkedBlockingQueue源码解析

    目录LinkedBlockingQueue概述类图结构及重要字段构造器出队和入队操作入队enqueue出队dequeue阻塞式操作E take() 阻塞式获取void put(E e) 阻塞式插入E poll(timeout, unit) 阻塞式超时获取boolean offer(e, timeou......

  2. js中this指向的问题与联系深入探究

    前言JavaScript 中最大的一个安全问题,也是最令人困惑的一个问题,就是在某些情况下this的值是如何确定的。有js基础的同学面对这个问题基本可以想到:this的指向和函数调用的方式相关。这当然是正确的,然而,这几种方式有什么联系吗?这是我接下来要说明的问题。this从哪里来this 是js的......

  3. 请谨慎使用 avaliable 方法来申请缓冲区

    问题今天开始尝试用 Java 写 http 服务器,开局就遇到 Bug。我先写了一个多线程的、BIO 的 http 服务器,其中接收请求的部分,会将请求的第一行打印出来。下面是浏览器发出的请求和控制台的输出情况。我们竟然收到了一个空的请求!!这是为什么呢?我解析请求的部分代码如下。// reques......

  4. Vue实现摇一摇功能(兼容ios13.3以上)

    最近做了个摇一摇类似的功能,使用的是shake.js,但在ios13.3之前的版本中可以触发摇一摇,之后的版本需要兼容,需要制作一个让用户能手动点击的弹框,才能使用户授权动作与方向的权限。(需使用https协议)温馨提示由于ios系统需要手动获取访问动作与方向的权限,为保障游戏的正常进行,请在访问提......

  5. js实现简单商品筛选功能

    本文实例为大家分享了js实现商品筛选功能的具体代码,供大家参考,具体内容如下应用场景:商品筛选Document* {margin: 0;padding: 0;list-style: none;text-decoration: none;}.choose {width: 500px;height: a......

  6. Java并发包源码学习系列:阻塞队列实现之SynchronousQueue源码解析

    目录SynchronousQueue概述 使用案例 类图结构 put与take方法 void put(E e) E take() Transfer 公平模式TransferQueue QNode transfer awaitFulfill tryCancel clean TransferQueue总......

  7. JVM笔记 -- Java跨平台和JVM跨语言

    学习JVM的重要性从上层应用程序到底层操作系统,到底有哪些东西?平时开发的应用程序主要基于各种框架,譬如Spring,SpringMVC,Mybatis,而各种框架又是基于Java API来实现的,Java API调用执行是在JVM上的,而JVM则是运行在操作系统上的,操作系统是在物理机器打交道的。......

  8. postgresql 中的序列nextval详解

    一、postgresql中的序列1.1 场景需求需要向下图一样,需要对产品编码编码设置一个序列。编码规则 SKU + 序列号:1.2 序列序列是基于bigint算法的,因此范围是不能超过一个八字节 整数的范围(-9223372036854775808 到 9223372036854775807)。由......

  9. 带有Python的音频处理(附带源码)

    由于博客播放不了音频,所以音频将以视频形式展现。公众号也正在进行抽书音频素材请点击这里进行观看往下拉就是文章地址有时,在进行编程时,我们需要进行一些音频处理。编程中最常用的音频处理任务包括–加载和保存音频文件,将音频文件拆分和追加到片段,使用不同的数据创建混合音频文件,操纵声音级别,应用一些过滤器以......

  10. c#生成缩略图代码

    public void SaveThumbnail(string path, string thumbnailPath, int newWidth, int newHeight){System.Drawing.Image i = System.Drawing.Image.FromFile(path)......