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

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

1. 貪心算法基礎

        貪心算法的解題方式是從可選的第一個解開始逐步到達目標解，如果在尋解的過程

        中因某種條件限制而停止向前，就得到一個近似解，因此貪心算法存在以下幾個問題：

        1) 貪心算法得到的解不一定是最優(yōu)解

        2) 不適用于最值問題

        3) 適用于部分約束條件的問題求解

        貪心算法的過程如下：

        1．建立數(shù)學模型來描述問題

        2．把求解的問題分成若干個子問題

        3．對每一子問題求解，得到子問題的局部最優(yōu)解

        4．把子問題的解局部最優(yōu)解合成原來解問題的一個解

        算法求解過程是首先從某一解向目標值出發(fā)，得到可行解的元素，然后合成所有解元素而得到一個可行解。

2. 找零問題

        1) 問題描述

        假設只有1 分、2 分、五分、1角、二角、五角、1元的硬幣。在超市結(jié)賬時，如果需要找零錢，收銀員希望將最少的硬幣數(shù)找給顧客。那么，給定需要找的零錢數(shù)目，如何求得最少的硬幣數(shù)呢？

        2) 問題分析

        在找零的時候會有多種方案，當零錢為五角的時候，可以用一個五角的，也可以用兩個兩角的和一個一角的，還可以用五個一角的，還可以用一個兩角的和三個一角的， 因此在我們在求解這個問題的時候可以從這些角度來思考。

        3) 代碼實現(xiàn)

  def main():
    d = [0.01,0.02,0.05,0.1,0.2,0.5,1.0] # 存儲每種硬幣面值
    d_num = [] # 存儲每種硬幣的數(shù)量
    s = 0
    # 擁有的零錢總和
    temp = input('請輸入每種零錢的數(shù)量：')
    d_num0 = temp.split(" ")
    for i in range(0, len(d_num0)):
        d_num.append(int(d_num0[i]))
        s += d[i] * d_num[i] # 計算出收銀員擁有多少錢
    sum = float(input("請輸入需要找的零錢:"))
    if sum > s:
        # 當輸入的總金額比收銀員的總金額多時，無法進行找零
        print("數(shù)據(jù)有錯")
        return 0
    s = s - sum
    # 要想用的錢幣數(shù)量最少，那么需要利用所有面值大的錢幣，因此從數(shù)組的面值大的元素開始遍歷
    i = 6
    while i >= 0: 
        if sum >= d[i]:
            n = int(sum / d[i])
            if n >= d_num[i]:
                n = d_num[i]  # 更新n
            sum -= n * d[i] # 貪心的關鍵步驟，使sum動態(tài)的改變
            print("用了%d個%f元硬幣"%(n, d[i]))
        i -= 1
if __name__ == "__main__":
main()

        輸出結(jié)果為：

請輸入每種零錢的數(shù)量：14 12 13 13 23 13 6
請輸入需要找的零錢:1.3
用了1個1.000000元硬幣
用了1個0.200000元硬幣
用了1個0.100000元硬幣

        首先輸入了所有零錢的數(shù)量，然后計算出錢的總數(shù)，保證零錢能夠找零，然后進入下一步找零。為了保證找零的數(shù)量最小，使用大面值的硬幣，因此從大面值的硬幣開始遍歷，如果大面值無法滿足的時候再往下取，這個算法的關鍵就在于sum的值是動態(tài)改變的，根據(jù)改變后的sum值再去進行判斷，直到最后完成。

 3. 汽車加油問題

        一輛汽車加滿油后可行駛n公里。旅途中有若干個加油站。設計一個有效算法，指出應在哪些加油站?？考佑?，使沿途加油次數(shù)最少。 對于給定的n(n <= 5000)和k(k <= 1000)個加油站位置，編程計算最少加油次數(shù)。

        代碼如下：

 def petrol():
    n = 100
    k = 5
    d = [23,45,39,70,54,62]
    # 表示加油站之間的距離
    num = 0
    # 表示加油次數(shù)
    for i in range(k):
        if d[i] > n:
            print('沒有適合的')
            # 如果距離中得到任何一個數(shù)值大于n 則無法計算
            return 
    i, s = 0, 0
    # 利用s進行迭代
    while i <= k:
        s += d[i]
        if s >= n:
            # 當局部和大于n時則局部和更新為當前距離
            s = d[i]
            # 貪心意在令每一次加滿油之后跑盡可能多的距離
            num += 1
        i += 1
    print(num)
if __name__ == '__main__':
    petrol()

        輸出結(jié)果為：

4

        這道題我們首先要判斷當油量是滿的時候是否可以大于所有相鄰加油站之間的距離，然后開始迭代，使用while語句，如果i等于5的時候就退出循環(huán)，循環(huán)中當局部和大于n時就把局部和更新為當前距離，然后次數(shù)加一，直到退出循環(huán)。