今天一个研究生同学问我一个问题，问题如下：
超市有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)；
三、算法代码实现
有了上边的分解，那么实现算法代码就非常的轻而易举了`
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
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 |
四、算法测试结果
准备一个顾客排队序列和指定收银台数量，得到最小时间
|
1
2
|
customer_list = [6, 5, 3, 4, 2, 1]print(greedy(customer_list, 2)) |
五、算法复杂性分析
程序主要是花费在对各顾客所需服务时间的排序和贪心算法，即计算平均服务时间上面。其中，贪心算法部分只有一重循环影响时间复杂度，其时间复杂度为O(n)：而排序算法的时间复杂度为O(nlogn)。因此，综合来看算法的时间复杂度为O(nlogn)。
以上就是Python实现贪心算法的示例的详细内容，更多关于Python实现贪心算法的资料请关注服务器之家其它相关文章！
原文链接：https://blog.csdn.net/zjlwdqca/article/details/107130193
