-5

我必须编写一个函数来计算并返回我们可以从知识库中获得的最大收益，该知识库按级别存储在列表列表中。

要测试此功能，主要是：

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]
4

1 回答 1

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
于 2012-05-15T08:22:06.680 回答