Python貪心算法

陳新龍

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

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

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

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

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

貪心算法在對(duì)問(wèn)題求解時(shí)，不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，也不是從整體上去考慮，做出的只是在某種意義上的局部最優(yōu)解。從面值最大的硬幣開(kāi)始依次遞減，尋找可用的方法。一般貪心算法并不能保證是最佳的解決方法，這是因?yàn)椋嚎偸菑木植砍霭l(fā)沒(méi)有從整體考慮，只能確定某些問(wèn)題是有解的，優(yōu)點(diǎn)是算法簡(jiǎn)單。常用來(lái)解決求最大值或最小值的問(wèn)題。