在给定输入中找到最大路径

Question

在这里很难说出要问什么。这个问题是模棱两可，含糊，不完整，过于宽泛或夸张的，不能以目前的形式合理地回答。如需帮助澄清此问题以便可以重新打开，
请访问帮助中心。

8年前关闭。

我将其作为作业，我需要在python中进行。

Problem:
The Maximum Route is defined as the maximum total by traversing from the tip of the triangle to its base. Here the maximum route is (3+7+4+9) 23.

3
7 4
2 4 6
8 5 9 3

Now, given a certain triangle, my task is to find the Maximum Route for it.

不确定如何执行…。

Answer 1

我们可以使用回溯来解决此问题。为此，对于给定行中三角形的每个元素，我们必须确定当前元素与下一行中三个相邻邻居的和的最大值，或者

if elem = triangle[row][col] and the next row is triangle[row+1]

then backtrack_elem = max([elem + i for i in connected_neighbors of col

in row])

首先尝试找到一种确定方法 connected_neighbors of col in row

在位置的ELEM（行，列），连接在相邻行=下一个将被[next[col-1],next[col],next[col+1]]提供`col - 1

=0和col+1 < len(next)`。这是示例实现

>>> def neigh(n,sz):
    return [i for i in (n-1,n,n+1) if 0<=i<sz]

这将返回已连接邻居的索引。

现在我们可以写backtrack_elem = max([elem + i for i in connected_neighbors of col in row])为

triangle[row][i] = max([elem + next[n] for n in neigh(i,len(next))])

如果我们按行迭代三角形，并且curr是给定的行，则i是该行的ith col索引，则可以编写

curr[i]=max(next[n]+e for n in neigh(i,len(next)))

现在我们必须迭代三角形以一起读取当前行和下一行。这可以做到

for (curr,next) in zip(triangle[-2::-1],triangle[::-1]):

然后我们使用枚举生成索引元组和elem本身

for (i,e) in enumerate(curr):

然后聚在一起，我们有

>>> for (curr,next) in zip(triangle[-2::-1],triangle[::-1]):
    for (i,e) in enumerate(curr):
        curr[i]=max(next[n]+e for n in neigh(i,len(next)))

但是上述操作具有破坏性，我们必须创建原始三角形的副本并对其进行处理

route = triangle # This will not work, because in python copy is done by reference
route = triangle[:] #This will also not work, because triangle is a list of list
                    #and individual list would be copied with reference

所以我们必须使用deepcopy模块

import copy
route = copy.deepcopy(triangle) #This will work

并重写为

>>> for (curr,next) in zip(route[-2::-1],route[::-1]):
    for (i,e) in enumerate(curr):
        curr[i]=max(next[n]+e for n in neigh(i,len(next)))

我们最终得到了另一个三角形，其中每个元素都给出了最高的路线成本。要获得实际路线，我们必须使用原始三角形并向后计算

因此，对于索引处的elem来说[row,col]，最高的路由成本是route [row]
[col]。如果遵循最大路由，则下一个元素应该是连接的邻居，并且路由开销应该是route [row] [col]-orig [row]
[col]。如果我们逐行迭代，我们可以写成

i=[x for x in neigh(next,i) if x == curr[i]-orig[i]][0]
orig[i]

并且我们应该从峰值元素开始向下循环。因此，我们有

>>> for (curr,next,orig) in zip(route,route[1:],triangle):
    print orig[i],
    i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]

让我们举一个复杂的例子，因为您的例子太微不足道了，无法解决

>>> triangle=[
          [3],
          [7, 4],
          [2, 4, 6],
          [8, 5, 9, 3],
          [15,10,2, 7, 8]
         ]

>>> route=copy.deepcopy(triangle) # Create a Copy

生成路线

>>> for (curr,next) in zip(route[-2::-1],route[::-1]):
    for (i,e) in enumerate(curr):
        curr[i]=max(next[n]+e for n in neigh(i,len(next)))


>>> route
[[37], [34, 31], [25, 27, 26], [23, 20, 19, 11], [15, 10, 2, 7, 8]]

最后我们计算出路线

>>> def enroute(triangle):
    route=copy.deepcopy(triangle) # Create a Copy
    # Generating the Route
    for (curr,next) in zip(route[-2::-1],route[::-1]): #Read the curr and next row
        for (i,e) in enumerate(curr):
            #Backtrack calculation
            curr[i]=max(next[n]+e for n in neigh(i,len(next)))
    path=[] #Start with the peak elem
    for (curr,next,orig) in zip(route,route[1:],triangle): #Read the curr, next and orig row
        path.append(orig[i])
        i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]
    path.append(triangle[-1][i]) #Don't forget the last row which
    return (route[0],path)

为了测试我们的三角形

>>> enroute(triangle)
([37], [3, 7, 4, 8, 15])

---

通过阅读jamylak的评论，我意识到这个问题类似于Euler
18，但是区别在于表示形式。欧拉18中的问题考虑一个金字塔，因为该问题中的问题是直角三角形。当您可以阅读我对他的评论的答复时，我解释了结果不同的原因。但是，可以很容易地将此​​问题移植到与Euler
18一起使用的地方。这是端口

>>> def enroute(triangle,neigh=lambda n,sz:[i for i in (n-1,n,n+1) if 0<=i<sz]):
    route=copy.deepcopy(triangle) # Create a Copy
    # Generating the Route
    for (curr,next) in zip(route[-2::-1],route[::-1]): #Read the curr and next row
        for (i,e) in enumerate(curr):
            #Backtrack calculation
            curr[i]=max(next[n]+e for n in neigh(i,len(next)))
    path=[] #Start with the peak elem
    for (curr,next,orig) in zip(route,route[1:],triangle): #Read the curr, next and orig row
        path.append(orig[i])
        i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]
    path.append(triangle[-1][i]) #Don't forget the last row which
    return (route[0],path)

>>> enroute(t1) # For Right angle triangle
([1116], [75, 64, 82, 87, 82, 75, 77, 65, 41, 72, 71, 70, 91, 66, 98])
>>> enroute(t1,neigh=lambda n,sz:[i for i in (n,n+1) if i<sz]) # For a Pyramid
([1074], [75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93])
>>>