Python最大收益

Question

我必須編寫一個函數，計算並返回我們可以從列表中的每個級別存儲的知識庫中實現的最大收益 。

爲了測試這個功能主要是：

if __name__ == "__main__": 
    l0 = [[7], [3,8], [8,1,0], [2,7,4,4], [4,5,2,6,5]] 
    l1 = [[11], [7,32], [14,14,14], [0,1,2,3], [5,99,1,2,7], 
     [0,25,9,45, 54,1], [99,88,77,66,55,44,33]] 
>>>30 
>>>270 

我試圖從底部到頂部開始，還有沒有其他的解決辦法？

你能想象像一棵樹

[7] 
    [3,8] 
[8,1,0] 
[2,7,4,4] 

等等... 我想達到的是有最大的好處步行列表，選用的權重由該數給出列表中，我曾經也有最大化我的路

我已經寫了這個解決方案

def maxpath(listN): 
    liv = len(listN) -1 
    return calcl(listN,liv) 

def calcl(listN,liv): 
    if liv == 0: 
    return listN[0] 
    listN[liv-1] = [(listN[liv-1][i]+listN[liv][i+1],listN[liv-1][i]+listN[liv][i]) \ 
       [ listN[liv][i] > listN[liv][i+1] ] for i in range(0,liv)] 
    return calcl(listN,liv-1) 

print(maxpath(l0)) 
print(maxpath(l1)) 

#output 
[30] 
[270] 

Answer 1

可能的路線通過樹的數量是2**rows 。到給定節點的可能路由的數量由二項式展開給出。您可以非常簡單地從樹的頭部增加可能的路徑，每個節點只有兩個可能的下一步移動，它們在列表中的索引與當前位置相同或多一個。

解決此問題的一種簡單方法是爲給定數量的行生成所有可能的路徑。 create_paths()這樣做，通過樹返回所有可能的路線。功能max_cost()使用此功能評估所有路線與成本樹，並返回最昂貴路線的值。我讓你獲得實際的路線了（不是很辛苦。）:)

L_0 = [[7], [3,8], [8,1,0], [2,7,4,4], [4,5,2,6,5]] 
L_1 = [[11], [7,32], [14,14,14], [0,1,2,3], [5,99,1,2,7], 
     [0,25,9,45, 54,1], [99,88,77,66,55,44,33]] 

def create_paths(rows): 
    new_paths = [] 
    paths = [[0]] 
    for row in xrange(rows): 
     for path in paths: 
      new_paths.append(path+[path[-1]]) 
      new_paths.append(path+[path[-1]+1]) 
     paths = new_paths 
     new_paths = [] 
    return paths 

def max_cost(tree): 
    costs = [] 
    paths = create_paths(len(tree)-1) 
    for path in paths: 
     costs.append(sum([tree[i][j] for i, j in enumerate(path)])) 
    return max(costs) 

print max_cost(L_0) 
print max_cost(L_1) 

#output: 
30 
270