貪心算法

貪心算法（又稱貪婪算法）是指，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。

貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個(gè)狀態(tài)以前的過程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

基本思路

思想

貪心算法的基本思路是從問題的某一個(gè)初始解出發(fā)一步一步地進(jìn)行，根據(jù)某個(gè)優(yōu)化測度，每一步都要確保能獲得局部最優(yōu)解。每一步只考慮一個(gè)數(shù)據(jù)，他的選取應(yīng)該滿足局部優(yōu)化的條件。若下一個(gè)數(shù)據(jù)和部分最優(yōu)解連在一起不再是可行解時(shí)，就不把該數(shù)據(jù)添加到部分解中，直到把所有數(shù)據(jù)枚舉完，或者不能再添加算法停止 。

步驟

1. 遍歷初始集合X中的備選元素
2. 利用貪心策略在X中確定一個(gè)元素，并將其加入到可行解S中
3. 得到可行解S

P即為貪心策略，用來選擇符合條件的元素。

例子——硬幣找零

假設(shè)某國硬幣面值有1,5,10,25,100元五種面額，若店員為顧客找零時(shí)，需要給顧客找零a=36元，求硬幣數(shù)最少的情況。

這里我們的貪心策略為：

先找到最接近a的值，然后對(duì)a進(jìn)行更新，然后進(jìn)行循環(huán)。

代碼實(shí)現(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 out
a = 36
print(shortNum(a))

例子——任務(wù)規(guī)劃

問題描述：

輸入為任務(wù)集合X= [r1,r2,r3,...,rn],每個(gè)任務(wù)ri,都對(duì)應(yīng)著一個(gè)起始時(shí)間ai與結(jié)束時(shí)間bi

要求輸出為最多的相容的任務(wù)集。

 如上圖，r1與r2相容，r3與r1和r2都不相容。

那么這里的貪心策略我們可以設(shè)為：

1. 先將結(jié)束時(shí)間最短的任務(wù)加入到S中，
2. 再從剩下的任務(wù)的任務(wù)中選擇結(jié)束時(shí)間最短的，且判斷與S集合中的任務(wù)是否相容
3. 若不相容，則換下一個(gè)時(shí)間最短的任務(wù)，并進(jìn)行比較
4. 循環(huán)，直至X為空。

代碼實(shí)現(xiàn)

# 任務(wù)規(guī)劃
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())
# 根據(jù)bi進(jìn)行排序，結(jié)束時(shí)間早的在前面（冒泡排序）
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 貪心算法的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于python 貪心算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論