2

我有这个作为家庭作业，我需要在 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.

不知道该怎么做......

4

4 回答 4

3

我们可以使用回溯来解决这个问题。要对任何给定行中三角形的每个元素执行此操作，我们必须确定当前元素和下一行中三个连接的相邻元素之和的最大值，或者

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

对于位置 (row,col) 中的元素，将[next[col-1],next[col],next[col+1]]提供row = next 中的连接邻居，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 是该行的第 i 个 col 索引，那么我们可以写

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

现在我们必须迭代读取当前行和下一行的三角形。这可以作为

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

然后我们使用 enumerate 生成一个索引元组和元素本身

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

并将 traverse 重写为

>>> 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)))

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

所以对于 index 处的元素[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，但不同之处在于表示。Euler 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])
>>>
于 2012-04-07T12:13:53.330 回答
2

即使这是家庭作业，@abhijit 也给出了答案，所以我也会！

要理解这一点，您需要阅读 python 生成器，可能需要谷歌搜索；）

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

第一步是找到所有可能的路线

>>> def routes(rows,current_row=0,start=0): 
        for i,num in enumerate(rows[current_row]): #gets the index and number of each number in the row
            if abs(i-start) > 1:   # Checks if it is within 1 number radius, if not it skips this one. Use if not (0 <= (i-start) < 2) to check in pyramid
                continue
            if current_row == len(rows) - 1: # We are iterating through the last row so simply yield the number as it has no children
                yield [num]
            else:
                for child in routes(rows,current_row+1,i): #This is not the last row so get all children of this number and yield them
                    yield [num] + child

这给

>>> list(routes(triangle))
[[3, 7, 2, 8], [3, 7, 2, 5], [3, 7, 4, 8], [3, 7, 4, 5], [3, 7, 4, 9], [3, 4, 2, 8], [3, 4, 2, 5], [3, 4, 4, 8], [3, 4, 4, 5], [3, 4, 4, 9], [3, 4, 6, 5], [3, 4, 6, 9], [3, 4, 6, 3]]

现在获取最大值很简单，max 接受生成器，因为它们是可迭代的，因此我们不需要将其转换为列表。

>>> max(routes(triangle),key=sum)
[3, 7, 4, 9]
于 2012-04-07T13:42:54.240 回答
1

我会给你一些关于这个具体案例的提示。尝试自己为 n 层三角形创建一个广义函数。

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

possible_roads={}

for i1 in range(1):
    for i2 in range(max(i1-1,0),i1+2):
        for i3 in range(max(i2-1,0),i2+2):
            for i4 in range(max(i3-1,0),i3+2):
                road=(triangle[0][i1],triangle[1][i2],triangle[2][i3],triangle[3][i4])
                possible_roads[road]=sum(road)

print "Best road: %s (sum: %s)" % (max(possible_roads), possible_roads[max(possible_roads)])

[编辑]因为每个人都在这里发布他们的答案是我的。

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

def generate_backtrack(triangle):
    n=len(triangle)
    routes=[[{'pos':i,'val':triangle[n-1][i]}] for i in range(n)]
    while n!=1:
        base_routes=[]
        for idx in range(len(routes)):
            i=routes[idx][-1]['pos'] #last node
            movements=range(
                                max(0,i-1),
                                min(i+2,n-1)
                            )
            for movement in movements:
                base_routes.append(routes[idx]+[{'pos':movement,'val':triangle[n-2][movement]}])

        n-=1
        routes=base_routes
    return [[k['val'] for k in j] for j in routes]

print sorted(generate_backtrack(triangle),key=sum,reverse=True)[0][::-1]
于 2012-04-07T10:40:38.147 回答
0

我的答案

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)

输出

l5=[
      [3],
      [7, 4],
      [2, 4, 6],
      [8, 5, 9, 3],
      [15,10,2, 7, 8]
     ]
print(maxpath(l5)
>>>[35]
于 2012-05-15T10:05:28.277 回答