本文实例讲述了Python贪心算法。分享给大家供大家参考,具体如下:
1. 找零钱问题:假设只有 1 分、 2 分、五分、 1 角、二角、 五角、 1元的硬币。在超市结账 时,如果 需要找零钱, 收银员希望将最少的硬币数找给顾客。那么,给定 需要找的零钱数目,如何求得最少的硬币数呢?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
# -*- coding:utf-8 -*-
def main():
d = [ 0.01 , 0.02 , 0.05 , 0.1 , 0.2 , 0.5 , 1.0 ] # 存储每种硬币面值
d_num = [] # 存储每种硬币的数量
s = 0
# 拥有的零钱总和
temp = raw_input ( '请输入每种零钱的数量:' )
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 ( raw_input ( "请输入需要找的零钱:" ))
if sum > s:
# 当输入的总金额比收银员的总金额多时,无法进行找零
print ( "数据有错" )
return 0
s = s - sum
# 要想用的钱币数量最少,那么需要利用所有面值大的钱币,因此从数组的面值大的元素开始遍历
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动态的改变,
print ( "用了%d个%f元硬币" % (n, d[i]))
i - = 1
if __name__ = = "__main__" :
main()
|
2. 求最大子数组之和问题:给定一个整数数组(数组元素有负有正),求其连续子数组之和的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
# -*- coding:utf-8 -*-
def main():
s = [ 12 , - 4 , 32 , - 36 , 12 , 6 , - 6 ]
print ( "定义的数组为:" ,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 ( "最大子数组和为:" ,s_max)
if __name__ = = "__main__" :
main()
|
3. 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。 对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置,编程计算最少加油次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
# 设汽车加满油后可行驶n公里,且旅途中有k个加油站
def greedy():
n = 100
k = 5
d = [ 50 , 80 , 39 , 60 , 40 , 32 ]
# 表示加油站之间的距离
num = 0
# 表示加油次数
for i in range (k):
if d[i] > n:
print ( 'no solution' )
# 如果距离中得到任何一个数值大于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__' :
greedy()
|
希望本文所述对大家Python程序设计有所帮助。
原文链接:https://blog.csdn.net/wangbowj123/article/details/78335203