上QQ阅读APP看书，第一时间看更新
3.4.3 实践演练——解决“汽车加油”问题
1．问题描述
一辆汽车加满油后可行驶n千米，旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n(n≤ 5000)千米和k(k≤1000)个加油站位置，编程计算最少加油次数。
2．具体实现
下面的实例文件jiayou.py演示使用贪心算法解决“汽车加油”问题的过程。
源码路径：daima\第3章\jiayou.py
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()
执行后会输出：
3