python 貪心算法的實現(xiàn)
貪心算法
貪心算法(又稱貪婪算法)是指,在對問題求解時,總是做出在當(dāng)前看來是最好的選擇。也就是說,不從整體最優(yōu)上加以考慮,他所做出的是在某種意義上的局部最優(yōu)解。
貪心算法不是對所有問題都能得到整體最優(yōu)解,關(guān)鍵是貪心策略的選擇,選擇的貪心策略必須具備無后效性,即某個狀態(tài)以前的過程不會影響以后的狀態(tài),只與當(dāng)前狀態(tài)有關(guān)。
基本思路
思想
貪心算法的基本思路是從問題的某一個初始解出發(fā)一步一步地進(jìn)行,根據(jù)某個優(yōu)化測度,每一步都要確保能獲得局部最優(yōu)解。每一步只考慮一個數(shù)據(jù),他的選取應(yīng)該滿足局部優(yōu)化的條件。若下一個數(shù)據(jù)和部分最優(yōu)解連在一起不再是可行解時,就不把該數(shù)據(jù)添加到部分解中,直到把所有數(shù)據(jù)枚舉完,或者不能再添加算法停止 。
步驟
遍歷初始集合X中的備選元素 利用貪心策略在X中確定一個元素,并將其加入到可行解S中 得到可行解SP即為貪心策略,用來選擇符合條件的元素。
例子——硬幣找零
假設(shè)某國硬幣面值有1,5,10,25,100元五種面額,若店員為顧客找零時,需要給顧客找零a=36元,求硬幣數(shù)最少的情況。
這里我們的貪心策略為:
先找到最接近a的值,然后對a進(jìn)行更新,然后進(jìn)行循環(huán)。
代碼實現(xiàn)
def shortNum(a): coins = [1,5,10,25,100] out = [] coins = coins[::-1] for i in coins: num = a//i out=out+[i,]*num a = a-num*i if a<=0: break return outa = 36print(shortNum(a))
例子——任務(wù)規(guī)劃
問題描述:
輸入為任務(wù)集合X= [r1,r2,r3,...,rn],每個任務(wù)ri,都對應(yīng)著一個起始時間ai與結(jié)束時間bi
要求輸出為最多的相容的任務(wù)集。
如上圖,r1與r2相容,r3與r1和r2都不相容。
那么這里的貪心策略我們可以設(shè)為:
先將結(jié)束時間最短的任務(wù)加入到S中, 再從剩下的任務(wù)的任務(wù)中選擇結(jié)束時間最短的,且判斷與S集合中的任務(wù)是否相容 若不相容,則換下一個時間最短的任務(wù),并進(jìn)行比較 循環(huán),直至X為空。代碼實現(xiàn)
# 任務(wù)規(guī)劃from collections import OrderedDicttask = OrderedDict()task[’r1’] = [0,4]task[’r2’] = [5,8]task[’r3’] = [10,13]task[’r4’] = [15,18]task[’r5’] = [7,11]task[’r6’] = [2,6]task[’r7’] = [2,6]task[’r8’] = [2,6]task[’r9’] = [12,16]task[’r10’] = [12,16]task[’r11’] = [12,16]task[’r12’] = [0,3]listTask = list(task.items())# 根據(jù)bi進(jìn)行排序,結(jié)束時間早的在前面(冒泡排序)for i in range(len(listTask)-1): for j in range(len(listTask)-i-1): if listTask[j][1][1] > listTask[j+1][1][1]: listTask[j],listTask[j+1]=listTask[j+1],listTask[j]print(listTask)out = []out.append(listTask.pop(0))def isValid(temp,out): for k in range(len(out)): if temp[1][0]<out[k][1][1]: # 相交 return False return Truefor j in range(len(listTask)): temp = listTask.pop(0) # 判斷是否相交 # 相交則continue # 不相交則out.append(temp) for k in range(len(out)): if isValid(temp,out): out.append(temp) # else:continue 語句可以不寫 else: continueprint(out)
以上就是python 貪心算法的實現(xiàn)的詳細(xì)內(nèi)容,更多關(guān)于python 貪心算法的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章!
相關(guān)文章:
1. XML入門的常見問題(三)2. XML基本概念XPath、XSLT與XQuery函數(shù)介紹3. WML的簡單例子及編輯、測試方法第1/2頁4. el-input無法輸入的問題和表單驗證失敗問題解決5. 關(guān)于html嵌入xml數(shù)據(jù)島如何穿過樹形結(jié)構(gòu)關(guān)系的問題6. CSS3實例分享之多重背景的實現(xiàn)(Multiple backgrounds)7. 不要在HTML中濫用div8. vue實現(xiàn)復(fù)制文字復(fù)制圖片實例詳解9. XML入門的常見問題(四)10. 前端html+css實現(xiàn)動態(tài)生日快樂代碼
