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

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

可以先讓前N個人付款 后邊顧客不斷找出付款時間最短的依次排到前N個顧客按時間最長到最短的后邊

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

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

def greedy(customer_list, n): # customer_time_list為第j個隊列上的某一個顧客的等待時間 # sum_customer_time_list是求和數(shù)組 # sum_customer_time_list[j]的值為第j個隊列上所有顧客的等待時間 # min_sum_customer_time為結(jié)賬最小時間 # 初始化一個大小為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到了最后一個結(jié)賬出口，重新歸零 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四、算法測試結(jié)果

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

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

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

以上就是Python實現(xiàn)貪心算法的示例的詳細內(nèi)容，更多關(guān)于Python實現(xiàn)貪心算法的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章！