溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
使用python 實現一個貪心算法？相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。
貪心算法
貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。
貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態以前的過程不會影響以后的狀態，只與當前狀態有關。
基本思路
思想
貪心算法的基本思路是從問題的某一個初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加算法停止 。
步驟
P即為貪心策略，用來選擇符合條件的元素。
例子——硬幣找零
假設某國硬幣面值有1,5,10,25,100元五種面額，若店員為顧客找零時，需要給顧客找零a=36元，求硬幣數最少的情況。
這里我們的貪心策略為：
先找到最接近a的值，然后對a進行更新，然后進行循環。
代碼實現
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 out
a = 36
print(shortNum(a))例子——任務規劃
問題描述：
輸入為任務集合X= [r1,r2,r3,...,rn],每個任務ri,都對應著一個起始時間ai與結束時間bi
要求輸出為最多的相容的任務集。
如上圖，r1與r2相容，r3與r1和r2都不相容。
那么這里的貪心策略我們可以設為：
代碼實現
# 任務規劃
from collections import OrderedDict
task = 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())
# 根據bi進行排序，結束時間早的在前面（冒泡排序）
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 True
for 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:
continue
print(out)看完上述內容，你們掌握使用python 實現一個貪心算法的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
