Python貪心算法

陳新龍

所謂貪心算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)加以考慮，它所做出的僅僅是在某種意義上的局部最優(yōu)解。下面讓我們來看一個經(jīng)典的例題。

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

這個找零錢的基本思路：每次都選擇面值不超過需要找給顧客的錢最大面值的硬幣。我們可以從面值最大的硬幣開始，然后依次遞減（圖1）。

首先定義列表d存儲已有幣值。并且定義d_num存儲每種幣值的數(shù)量。通過循環(huán)遍歷的方法計算出收銀員擁有錢的總金額并保存在變量S中，要找的零錢變量為sum。

當找零的金額比收銀員的總金額多時，無法進行找零，提示報錯。要想用的錢幣數(shù)量最少，我們從面值最大的幣值開始遍歷。這里也就是我們貪心算法的核心步驟。計算出每種硬幣所需要的數(shù)量，不斷地更新硬幣個數(shù)與硬幣面值，最終獲得一個符合要求的組合（圖2）。

貪心算法在對問題求解時，不是對所有問題都能得到整體最優(yōu)解，也不是從整體上去考慮，做出的只是在某種意義上的局部最優(yōu)解。從面值最大的硬幣開始依次遞減，尋找可用的方法。一般貪心算法并不能保證是最佳的解決方法，這是因為：總是從局部出發(fā)沒有從整體考慮，只能確定某些問題是有解的，優(yōu)點是算法簡單。常用來解決求最大值或最小值的問題。