使用python 實(shí)現(xiàn)一個(gè)貪心算法？相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策，為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法，通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。

目前創(chuàng)新互聯(lián)已為上千余家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁(yè)空間、網(wǎng)站托管、企業(yè)網(wǎng)站設(shè)計(jì)、綏陽(yáng)網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶(hù)導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶(hù)和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

貪心算法

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

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

基本思路

思想

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

步驟

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

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

例子——硬幣找零

假設(shè)某國(guó)硬幣面值有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ǎng)站欄目：使用python實(shí)現(xiàn)一個(gè)貪心算法-創(chuàng)新互聯(lián)
文章URL：http://weahome.cn/article/ddohhh.html