Pythonmax benefi

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