怎麼用Python實現貪心演算法

我們知道，貪心演算法的原理是在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優加以考慮，他所做的僅是在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，但對範圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。

特性：貪心演算法採用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以貪婪法不要回溯。能夠用貪心演算法求解的問題一般具有兩個重要特性：貪心選擇性質和最優子結構性質。

如題：給出一組活動，告訴每個活動的開始時間和結束時間，要求出算出能參加的最多活動的數量或活動的起止時間

貪心演算法思路：

用兩個陣列s，f分別儲存活動的起止時間，根據活動的結束時間對活動進行一個非減的活動序列，同樣活動的開始時間list也要做對應的調整，這裡博主是透過冒泡排序同步交換的，舉例：活動（1，4）（2，3）（3，5）那麼我們得到的

s = [2,1,3]
f = [3,4,5]

透過比較下一個活動的開始時間與上一個活動的結束時間的大小關係，確定這兩個活動是否是相容的，如果開始時間大於結束時間，則相容，反之不相容,代碼如下#用冒泡排序對結束時間進行排序，同時得到對應的開始時間的list

def bubble_sort(s,f):
  for i in range(len(f)):
    for j in range(0,len(f)-i-1):
      if f[j] > f[j+1]:
        f[j], f[j+1] = f[j+1],f[j]
        s[j],s[j+1] = s[j+1],s[j]
  return s,f
 
def greedy(s,f,n):
  a = [True for x in range(n)]
  #初始选择第一个活动
  j = 0
  for i in range(1,n):
    #如果下一个活动的开始时间大于等于上个活动的结束时间
    if s[i] >= f[j]:
      a[i] = True
      j = i
    else:
      a[i] = False
  return a
 
n = int(input())
arr = input().split()
s = []
f = []
for ar in arr:
  ar = ar[1:-1]
  start = int(ar.split(',')[0])
  end = int(ar.split(',')[1])
  s.append(start)
  f.append(end)
 
s,f = bubble_sort(s,f)
A = greedy(s,f,n)
 
res = []
for k in range(len(A)):
  if A[k]:
    res.append('({},{})'.format(s[k],f[k]))
print(' '.join(res))

相信看了這些案例你已經掌握了方法，更多精彩請關注php中文網其它相關文章！

相關閱讀：

php如何實作堆疊資料結構以及括號匹配演算法的程式碼範例詳解

php中最簡單的字串匹配演算法，php匹配演算法_PHP教程

最簡單的php中字串匹配演算法教程

以上是怎麼用Python實現貪心演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！