快捷導(dǎo)航

Python實(shí)現(xiàn)貪心算法的示例

更新時(shí)間：2021年04月01日 16:46:48 作者：zjlwdqca

這篇文章主要介紹了Python實(shí)現(xiàn)貪心算法的示例，幫助大家更好的理解和學(xué)習(xí)使用python，感興趣的朋友可以了解下

今天一個(gè)研究生同學(xué)問(wèn)我一個(gè)問(wèn)題，問(wèn)題如下：
超市有m個(gè)顧客要結(jié)賬，每個(gè)顧客結(jié)賬的時(shí)間為Ti（ i取值從1到m）。超市有n個(gè)結(jié)賬出口，請(qǐng)問(wèn)全部顧客怎么選擇出口，可以最早完成全部顧客的結(jié)賬，并用代碼實(shí)現(xiàn)。
其實(shí)利用的就是貪心算法來(lái)解決這個(gè)問(wèn)題，那么，什么是貪心算法？怎么用貪心算法解決這個(gè)問(wèn)題？讓我一一道來(lái)。

一、貪心算法簡(jiǎn)介

貪心算法是一種對(duì)某些求最優(yōu)解問(wèn)題的更簡(jiǎn)單、更迅速的設(shè)計(jì)技術(shù)。貪心算法的特點(diǎn)是一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測(cè)度作最優(yōu)選擇，而不考慮各種可能的整體情況，省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪心算法采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇，就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，通過(guò)每一步貪心選擇，可得到問(wèn)題的一個(gè)最優(yōu)解。雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的，所以貪心算法不要回溯。

二、解決思路

1.同學(xué)導(dǎo)師給的思路

可以先讓前N個(gè)人付款后邊顧客不斷找出付款時(shí)間最短的依次排到前N個(gè)顧客按時(shí)間最長(zhǎng)到最短的后邊

2.問(wèn)題分解

可以先假設(shè)只有一個(gè)收銀臺(tái)，那么我們可以很快的反應(yīng)過(guò)來(lái)，最優(yōu)的順序就是按時(shí)間由小到大依次進(jìn)行。
即最優(yōu)解為A={t(1)，t(2)，…．t(n)}(其中t(i)為第i個(gè)用戶需要的服務(wù)時(shí)間)，則每個(gè)用戶等待時(shí)間為：
T(1)=t(1)；T(2)=t(1)+t(2)；…T(n)：t(1)+t(2)+t(3)+……t(n)；
那么總等待時(shí)問(wèn)，即最優(yōu)值為：
TA=n*t(1)+(n-1)*t(2)+…+(n+1-j)t(i)+…2t(n-1)+t(n)；

三、算法代碼實(shí)現(xiàn)

有了上邊的分解，那么實(shí)現(xiàn)算法代碼就非常的輕而易舉了`

def greedy(customer_list, n):
 # customer_time_list為第j個(gè)隊(duì)列上的某一個(gè)顧客的等待時(shí)間
 # sum_customer_time_list是求和數(shù)組
 # sum_customer_time_list[j]的值為第j個(gè)隊(duì)列上所有顧客的等待時(shí)間
 # min_sum_customer_time為結(jié)賬最小時(shí)間
 # 初始化一個(gè)大小為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
 # 顧客的數(shù)量
 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到了最后一個(gè)結(jié)賬出口，重新歸零
  if j == n:
   j = 0
 # 匯總最小總時(shí)間
 k = 0
 while k < n:
  min_sum_customer_time += sum_customer_time_list[k]
  k += 1
 return min_sum_customer_time

四、算法測(cè)試結(jié)果

準(zhǔn)備一個(gè)顧客排隊(duì)序列和指定收銀臺(tái)數(shù)量，得到最小時(shí)間

customer_list = [6, 5, 3, 4, 2, 1]
print(greedy(customer_list, 2))

五、算法復(fù)雜性分析

程序主要是花費(fèi)在對(duì)各顧客所需服務(wù)時(shí)間的排序和貪心算法，即計(jì)算平均服務(wù)時(shí)間上面。其中，貪心算法部分只有一重循環(huán)影響時(shí)間復(fù)雜度，其時(shí)間復(fù)雜度為O(n)：而排序算法的時(shí)間復(fù)雜度為O(nlogn)。因此，綜合來(lái)看算法的時(shí)間復(fù)雜度為O(nlogn)。

以上就是Python實(shí)現(xiàn)貪心算法的示例的詳細(xì)內(nèi)容，更多關(guān)于Python實(shí)現(xiàn)貪心算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: