Python視頻教程之Python貪心算法實(shí)例小結(jié)
加入技術(shù)交流群
掃碼加入
和技術(shù)大咖面對(duì)面交流
海量資料庫(kù)查詢
本篇文章扣丁學(xué)堂Python培訓(xùn)小編主要和大家分享一下Python貪心算法實(shí)例，文章中結(jié)合三個(gè)常見(jiàn)實(shí)例分析了貪心算法的原理及解決具體問(wèn)題的相關(guān)使用技巧，喜歡Python開(kāi)發(fā)的小伙伴可以隨著小編一起來(lái)了解下。
本文實(shí)例講述了Python貪心算法。分享給大家供大家參考，具體如下：
1、找零錢(qián)問(wèn)題：假設(shè)只有 1 分、 2 分、五分、 1 角、二角、 五角、 1元的硬幣。在超市結(jié)賬 時(shí)，如果 需要找零錢(qián)， 收銀員希望將最少的硬幣數(shù)找給顧客。那么，給定 需要找的零錢(qián)數(shù)目，如何求得最少的硬幣數(shù)呢？
# -*- coding:utf-8 -*-
def main():
d = [0.01,0.02,0.05,0.1,0.2,0.5,1.0] # 存儲(chǔ)每種硬幣面值
d_num = [] # 存儲(chǔ)每種硬幣的數(shù)量
s = 0
# 擁有的零錢(qián)總和
temp = raw_input('請(qǐng)輸入每種零錢(qián)的數(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] # 計(jì)算出收銀員擁有多少錢(qián)
sum = float(raw_input("請(qǐng)輸入需要找的零錢(qián):"))
if sum > s:
# 當(dāng)輸入的總金額比收銀員的總金額多時(shí)，無(wú)法進(jìn)行找零
print("數(shù)據(jù)有錯(cuò)")
return 0
s = s - sum
# 要想用的錢(qián)幣數(shù)量最少，那么需要利用所有面值大的錢(qián)幣，因此從數(shù)組的面值大的元素開(kāi)始遍歷
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] # 貪心的關(guān)鍵步驟，令sum動(dòng)態(tài)的改變，
print("用了%d個(gè)%f元硬幣"%(n, d[i]))
i -= 1
if __name__ == "__main__":
main()2、 求最大子數(shù)組之和問(wèn)題：給定一個(gè)整數(shù)數(shù)組（數(shù)組元素有負(fù)有正），求其連續(xù)子數(shù)組之和的最大值。
# -*- coding:utf-8 -*-
def main():
s = [12,-4,32,-36,12,6,-6]
print("定義的數(shù)組為：",s)
s_max, s_sum = 0, 0
for i in range(len(s)):
s_sum += s[i]
if s_sum >= s_max:
s_max = s_sum # 不斷更新迭代s_max的值，盡可能的令其最大
elif s_sum < 0:
s_sum = 0
print("最大子數(shù)組和為：",s_max)
if __name__ == "__main__":
main()
3、一輛汽車(chē)加滿油后可行駛n公里。旅途中有若干個(gè)加油站。設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站?？考佑停寡赝炯佑痛螖?shù)最少。 對(duì)于給定的n(n <= 5000)和k(k <= 1000)個(gè)加油站位置，編程計(jì)算最少加油次數(shù)。
# 設(shè)汽車(chē)加滿油后可行駛n公里，且旅途中有k個(gè)加油站
def greedy():
n = 100
k = 5
d = [50,80,39,60,40,32]
# 表示加油站之間的距離
num = 0
# 表示加油次數(shù)
for i in range(k):
if d[i] > n:
print('no solution')
# 如果距離中得到任何一個(gè)數(shù)值大于n 則無(wú)法計(jì)算
return
i, s = 0, 0
# 利用s進(jìn)行迭代
while i <= k:
s += d[i]
if s >= n:
# 當(dāng)局部和大于n時(shí)則局部和更新為當(dāng)前距離
s = d[i]
# 貪心意在令每一次加滿油之后跑盡可能多的距離
num += 1
i += 1
print(num)
if __name__ == '__main__':
greedy()以上就是扣丁學(xué)堂Python在線教程小編給大家分享的Python貪心算法實(shí)例小結(jié)，希望對(duì)小伙伴們有所幫助，想要了解更多內(nèi)容的小伙伴可以登錄扣丁學(xué)堂官網(wǎng)咨詢?？鄱W(xué)堂是專(zhuān)業(yè)的Python培訓(xùn)機(jī)構(gòu)，不僅有專(zhuān)業(yè)的老師和與時(shí)俱進(jìn)的課程體系，還有大量的Python在線教程供學(xué)員觀看學(xué)習(xí)，想要學(xué)習(xí)Python的小伙伴快快行動(dòng)吧。扣丁學(xué)堂python學(xué)習(xí)交流群：816572891。微信號(hào)：codingbb
*博客內(nèi)容為網(wǎng)友個(gè)人發(fā)布，僅代表博主個(gè)人觀點(diǎn)，如有侵權(quán)請(qǐng)聯(lián)系工作人員刪除。
