淺談Python實(shí)現(xiàn)貪心算法與活動(dòng)安排問題
貪心算法
原理:在對(duì)問題求解時(shí),總是做出在當(dāng)前看來是最好的選擇。也就是說,不從整體最優(yōu)上加以考慮,他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解,但對(duì)范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。
特性:貪心算法采用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇就將所求問題簡(jiǎn)化為一個(gè)規(guī)模更小的子問題,通過每一步貪心選擇,可得到問題的一個(gè)最優(yōu)解,雖然每一步上都要保證能獲得局部最優(yōu)解,但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的,所以貪婪法不要回溯。能夠用貪心算法求解的問題一般具有兩個(gè)重要特性:貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。
如題:給出一組活動(dòng),告訴每個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間,要求出算出能參加的最多活動(dòng)的數(shù)量或者活動(dòng)的起止時(shí)間
貪心算法思路:
用兩個(gè)數(shù)組s,f分別存儲(chǔ)活動(dòng)的起止時(shí)間,根據(jù)活動(dòng)的結(jié)束時(shí)間對(duì)活動(dòng)進(jìn)行一個(gè)非減的活動(dòng)序列,同樣活動(dòng)的開始時(shí)間list也要做對(duì)應(yīng)的調(diào)整,這里博主是通過冒泡排序同步交換的,舉例:活動(dòng)(1,4)(2,3)(3,5)那么我們得到的
s = [2,1,3] f = [3,4,5]
通過比較下一個(gè)活動(dòng)的開始時(shí)間與上一個(gè)活動(dòng)的結(jié)束時(shí)間的大小關(guān)系,確定這兩個(gè)活動(dòng)是否是相容的,如果開始時(shí)間大于結(jié)束時(shí)間,則相容,反之不相容,代碼如下
#用冒泡排序?qū)Y(jié)束時(shí)間進(jìn)行排序,同時(shí)得到對(duì)應(yīng)的開始時(shí)間的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)] #初始選擇第一個(gè)活動(dòng) j = 0 for i in range(1,n): #如果下一個(gè)活動(dòng)的開始時(shí)間大于等于上個(gè)活動(dòng)的結(jié)束時(shí)間 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個(gè)活動(dòng)的起止時(shí)間,輸出相容的活動(dòng)的起止時(shí)間
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
深入理解Python虛擬機(jī)中元組(tuple)的實(shí)現(xiàn)原理及源碼
在本篇文章當(dāng)中主要給大家介紹?cpython?虛擬機(jī)當(dāng)中針對(duì)列表的實(shí)現(xiàn),在?Python?中,tuple?是一種非常常用的數(shù)據(jù)類型,在本篇文章當(dāng)中將深入去分析這一點(diǎn)是如何實(shí)現(xiàn)的2023-03-03基于python list對(duì)象中嵌套元組使用sort時(shí)的排序方法
下面小編就為大家分享一篇基于python list對(duì)象中嵌套元組使用sort時(shí)的排序方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-04-04在Python中f-string的幾個(gè)技巧,你都知道嗎
f-string想必很多Python用戶都基礎(chǔ)性的使用過,但是百分之九十的人不知道?在Python中f-string的幾個(gè)技巧,今天就帶大家一起看看Python f-string技巧大全,需要的朋友參考下吧2021-10-10解決keras加入lambda層時(shí)shape的問題
這篇文章主要介紹了解決keras加入lambda層時(shí)shape的問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-06-06Python numpy大矩陣運(yùn)算內(nèi)存不足如何解決
這篇文章主要介紹了Python numpy大矩陣運(yùn)算內(nèi)存不足如何解決,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11Python開發(fā)的十個(gè)小貼士和技巧及長(zhǎng)常犯錯(cuò)誤
這篇文章主要介紹了Python開發(fā)的十個(gè)小貼士和技巧,其中一些是初學(xué)這門語言常常會(huì)犯的錯(cuò)誤,小編給大家一一列舉出來了,需要的朋友可以參考下2018-09-09