欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python 貪心算法的實現

 更新時間:2020年09月18日 17:17:38   作者:Achilles_Heel  
這篇文章主要介紹了python 貪心算法的實現,幫助大家更好的理解和學習python,感興趣的朋友可以了解下

貪心算法

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

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

基本思路

思想

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

步驟

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

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

例子——硬幣找零

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

這里我們的貪心策略為:

先找到最接近a的值,然后對a進行更新,然后進行循環(huá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))

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

問題描述:

輸入為任務集合X= [r1,r2,r3,...,rn],每個任務ri,都對應著一個起始時間ai與結束時間bi

要求輸出為最多的相容的任務集。

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

那么這里的貪心策略我們可以設為:

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

代碼實現

# 任務規(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())
# 根據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 貪心算法的實現的詳細內容,更多關于python 貪心算法的資料請關注腳本之家其它相關文章!

相關文章

  • Python內置模塊ConfigParser實現配置讀寫功能的方法

    Python內置模塊ConfigParser實現配置讀寫功能的方法

    這篇文章主要介紹了Python內置模塊ConfigParser實現配置讀寫功能的方法,涉及Python使用ConfigParser模塊進行配置讀、寫、修改、刪除等操作的相關實現技巧,需要的朋友可以參考下
    2018-02-02
  • Python中的pygal安裝和繪制直方圖代碼分享

    Python中的pygal安裝和繪制直方圖代碼分享

    這篇文章主要介紹了Python中的pygal安裝和繪制直方圖代碼分享,具有一定借鑒價值,需要的朋友可以參考下。
    2017-12-12
  • 快速入手Python字符編碼

    快速入手Python字符編碼

    本文不談復雜的理論,就經驗教大家字符處理八字真言:確定編碼,同類交互。教大家快速戰(zhàn)勝Python字符編碼。
    2016-08-08
  • Python讀取Excel一列并計算所有對象出現次數的方法

    Python讀取Excel一列并計算所有對象出現次數的方法

    這篇文章主要給大家介紹了關于Python讀取Excel一列并計算所有對象出現次數的相關資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-09-09
  • 利用pandas合并多個excel的方法示例

    利用pandas合并多個excel的方法示例

    這篇文章主要介紹了利用pandas合并多個excel的方法示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2019-10-10
  • Python面向對象三大特征 封裝、繼承、多態(tài)

    Python面向對象三大特征 封裝、繼承、多態(tài)

    這篇文章主要介紹了Python面向對象三大特征 封裝、繼承、多態(tài),下面文章圍繞Python面向對象三大特征的相關資料展開具體內容,需要的朋友可以參考一下,希望對大家有所幫助
    2021-11-11
  • python處理excel繪制雷達圖

    python處理excel繪制雷達圖

    這篇文章主要為大家介紹了python處理excel繪制雷達圖的相關方法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-10-10
  • Python時間管理黑科技之datetime函數詳解

    Python時間管理黑科技之datetime函數詳解

    在Python中,datetime模塊是處理日期和時間的標準庫,它提供了一系列功能強大的函數和類,用于處理日期、時間、時間間隔等,本文將深入探討datetime模塊的使用方法,感興趣的可以了解下
    2023-08-08
  • python如何代碼集體右移

    python如何代碼集體右移

    在本篇文章里小編給各位分享的是一篇關于python如何代碼集體右移的相關知識點文章,需要的朋友們可以學習下。
    2020-07-07
  • python多進程實現進程間通信實例

    python多進程實現進程間通信實例

    這篇文章主要介紹了python多進程實現進程間通信實例,具有一定參考價值,需要的朋友可以了解下。
    2017-11-11

最新評論