Python實現貪心算法的示例

今天一個研究生同學問我一個問題,問題如下:
超市有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實現貪心算法的資料請關註WalkonNet其它相關文章!