淺談Python實現(xiàn)貪心算法與活動安排問題
貪心算法
原理：在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。
特性：貪心算法采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時不一定是最優(yōu)的，所以貪婪法不要回溯。能夠用貪心算法求解的問題一般具有兩個重要特性：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。
如題：給出一組活動，告訴每個活動的開始時間和結(jié)束時間，要求出算出能參加的最多活動的數(shù)量或者活動的起止時間
貪心算法思路：
用兩個數(shù)組s，f分別存儲活動的起止時間，根據(jù)活動的結(jié)束時間對活動進行一個非減的活動序列，同樣活動的開始時間list也要做對應的調(diào)整，這里博主是通過冒泡排序同步交換的，舉例：活動（1，4）（2，3）（3，5）那么我們得到的
s = [2,1,3] f = [3,4,5]
通過比較下一個活動的開始時間與上一個活動的結(jié)束時間的大小關系，確定這兩個活動是否是相容的，如果開始時間大于結(jié)束時間，則相容，反之不相容,代碼如下
#用冒泡排序?qū)Y(jié)束時間進行排序，同時得到對應的開始時間的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):
#如果下一個活動的開始時間大于等于上個活動的結(jié)束時間
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))
執(zhí)行結(jié)果如下：輸入11個活動的起止時間，輸出相容的活動的起止時間
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了Numpy的簡單用法小結(jié)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-08-08
這篇文章主要介紹了Python Django路徑配置實現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-11-11
這篇文章主要介紹了python用Configobj模塊讀取配置文件，幫助大家更好的利用python處理文件，感興趣的朋友可以了解下2020-09-09
pandas.DataFrame的for循環(huán)迭代的實現(xiàn)
本文主要介紹了pandas.DataFrame的for循環(huán)迭代的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-02-02
在本篇內(nèi)容里小編給大家整理的是關于python生成時間戳的簡單方法，需要的朋友們可以學習下。2020-07-07
這篇文章主要介紹了詳解Python中的條件,循環(huán)語句,包括while循環(huán)for循環(huán)，循環(huán)語句是學習各個編程語言的最基本的基礎知識,需要的朋友可以參考下2021-09-09
這篇文章主要介紹了python opencv 簡單閾值算法的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-08-08
這篇文章主要為大家詳細介紹了python保存網(wǎng)頁圖片到本地的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-07-07
這篇文章主要介紹了python刪除過期log文件，分享了相關代碼示例，小編覺得還是挺不錯的，具有一定借鑒價值，需要的朋友可以參考下2018-01-01
這篇文章主要介紹了python 實現(xiàn)ping測試延遲的兩種方法，幫助大家更好的理解和使用python，感興趣的朋友可以了解下2020-12-12