贪心算法思想
贪心算法从问题的某个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。
存在的问题
- 不能保证最后的解是最优的。
- 不能用来求最大解或最小解问题。
- 只能求满足某些约束条件的可行解范围。
基本思路
- 建立数学模型来描述问题。
- 把求解的问题分成若干个子问题。
- 对每一个子问题求解，得到子问题的局部最优解。
- 把子问题的局部最优解合并成原来问题的一个解。
基本过程
- 从问题的某一初始解出发。
- while 能向给定总目标前进一步。
- 求出可行解的一个解元素。
- 由所有解元素组合成问题的一个可行解。
“找零”问题
问题描述：假设只有 1 分、2 分、5 分、1 角、2 角、5 角、1 元面值的硬币。在超市结账时，如果需要找零钱，收银员希望将最少的硬币数找给顾客。那么，给定需要找的零钱数目，如何求得最少的硬币数？
def main():
d = [0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1.0] # 存储每种硬币的面值
d_num = [] # 存储每种硬币的数量
s = 0 # 拥有的零钱总和
temp = 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(input('请输入需要找的零钱：'))
assert s >= sum
# 从数组中最大面值的元素开始遍历
i = len(d) - 1
while i >= 0:
if sum >= d[i]:
n = int(sum / d[i])
if n >= d_num[i]:
n = d_num[i]
sum -= n * d[i]
print('用了%d个%f枚硬币'%(n, d[i]))
i -= 1
if __name__ == '__main__':
main()
请输入每种零钱的数量：5 5 5 3 2 2 1
请输入需要找的零钱：1.6
用了1个1.000000枚硬币
用了1个0.500000枚硬币
用了1个0.100000枚硬币
“汽车加油”问题
问题描述：一辆汽车加满油后可行驶 n 千米，旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的 n(n<=5000) 千米和 k(k<=1000) 个加油站位置，编程计算最少加油次数。
def greedy(n ,k, d):
num = 0 # 加油次数
for i in range(k):
if d[i] > n:
print('no solution')
return
i, s = 0, 0
while i <= k:
s += d[i]
if s >= n:
s = d[i]
num += 1
i += 1
print(num)
if __name__ == '__main__':
n = 100 # 加满油可行驶的距离
k = 5 # 加油站数量
d = [50, 80, 39, 60, 40, 32] # 加油站之间的距离
greedy(n, k, d) # 3
