python greedy 加油次數

題目要求：

'''
一輛汽車加滿油後可行駛n公裡。旅途中有若幹個加油站。
設計一個有效算法，指出應在哪些加油站停靠加油，使沿途加油次數最少。 
對于給定的n(n <= 5000)和k(k <= 1000)個加油站位置，程式設計計算最少加油次數
'''      

分析：

1、首先明确，一段路程，k個加油站，有k+1段路程。即： k=len(distance)-1

2、如果這k+1段路程中，任意一段路程大于n，回報空，此題結束。

3、如果k+1段路程都是小于n的。用while循環嵌套while循環，計算次數。

i為路程位置，length後每次加滿後要跑的距離，num為加油次數，都初始化為0.

裡面的while循環：以length長度為判斷是否循環條件

length=length+distance[i]，如果length小于n，i的位置往後移一位，繼續執行length=length+distance[i]，直到length大于等于n，跳出内部的while循環，num加1，length初始化為0。

外面的while循環：以i位置為判斷是否循環條件

length=length+distance[i]

當i小于k時， length=length+distance[i]，執行内部while循環移動i的位置，每次内部循環跳出，num加1，length初始化為0。直到i==k，跳出外循環。傳回最後的num

代碼：

def greedy(n,distance):
    #n是汽車加油加滿後能跑的最長裡程
    #distance是路程中各段距離清單
    #k是加油站個數

    k=len(distance)-1
    print('k',k)


    for i in range(k+1):
        if distance[i]>n:
            return
    i=0
    #length後每次加滿後要跑的距離
    length=0
    #num為加油次數
    num=0
    while i <k:
        print('i1',i)
        print('distance[i]',distance[i])
        length=length+distance[i]
        print('length0',length)
        while length<n:
            i=i+1
            print('i2',i)
            length=length+distance[i]
            print('length1',length)
            if length>= n:
                break
        num=num+1
        print('num0',num)
        length=0
        if i==k:
            break
    print('num',num)
    return num
if __name__ == '__main__':
    n=100
    distance=[50,80,39,60,40,32,10,50,80]
    result=greedy(n,distance)
    print('最少加油次數',result)      

運作結果

k 8

i1 0

distance[i] 50

length0 50

i2 1

length1 130

num0 1

i1 1

distance[i] 80

length0 80

i2 2

length1 119

num0 2

i1 2

distance[i] 39

length0 39

i2 3

length1 99

i2 4

length1 139

num0 3

i1 4

distance[i] 40

length0 40

i2 5

length1 72

i2 6

length1 82

i2 7

length1 132

num0 4

i1 7

distance[i] 50

length0 50

i2 8

length1 130

num0 5

num 5

最少加油次數 5