https://projecteuler.net/problem=18
给定一个整数三角形,问题是从上到下求最大路径和(路径中的所有数字必须相邻)。你知道吗
我有一个算法的想法:从最上面开始,计算左右路径的和(从左到下,从右到下),如果左和更大,跳到左边相邻的数字,如果右和更大,跳到右边相邻的数字,从当前数字开始重复算法,如此一直开到最下面一排。你知道吗
triangle = ['75', '9564', '174782', '18358710', '2004824765', '190123750334', '88027773076367', '9965042806167092', '414126568340807033', '41487233473237169429', '5371446525439152975114', '701133287773177839681757', '91715238171491435850272948', '6366046889536730731669874031', '046298272309709873933853600423']
maximumPath = [75]
maxSum = 75 #Start it with the starting element of the triangle.
def triNum(row, index): #Returns the number at given row, number in row
return(int(triangle[row][2*index:2*(index+1)])) #Nota bene: returns an integer.
def options(row, index): #Rows start at 0, index starts at 0
return(triNum(row+1, index), triNum(row+1, index+1))
def criticalPathSum(startRow, startIndex, direction):
critPath = []
if direction == 'left':
directionNum = 0
else:
directionNum = 1
sum = triNum(startRow, startIndex) #Starting sum of left and right paths is just the number at the start of both paths.
for i in range(startRow + 1, len(triangle)):
startIndex += directionNum
sum += triNum(i, startIndex)
critPath.append(triNum(i, startIndex))
#print(triNum(i, startIndex + directionNum))
return(sum, critPath)
pathIndex = 0
for row in range(0, len(triangle)-1):
print('These are my options: ' + str(options(row, pathIndex)))
print('Left Sum: ' + str(criticalPathSum(row, pathIndex, 'left')) + ', ' + 'Right Sum: ' + str(criticalPathSum(row, pathIndex, 'right')))
if criticalPathSum(row, pathIndex, 'left') > criticalPathSum(row, pathIndex, 'right'):
maximumPath.append(triNum(row + 1, pathIndex))
print('Left. ' + str(triNum(row + 1, pathIndex)))
else:
print('Right. ' + str(triNum(row + 1, pathIndex + 1)))
pathIndex += 1
maximumPath.append(triNum(row + 1, pathIndex))
maxSum += triNum(row + 1, pathIndex)
print('_______________________________')
print('\n')
print(maximumPath)
print(maxSum)
答案是1067,但我得到883。根据算法,这是最大路径:
[75, 95, 17, 35, 82, 75, 7, 16, 80, 37, 91, 17, 91, 67, 98].
你的算法是错误的:在一个三角形中
它太受
9
(总是向左)的诱惑而看不到最优的1+4+4+4
=13
路径。你知道吗这是许多错误的算法中的一个,测试数据被设计成失败的。您选择了所谓的“贪婪”算法,该算法在不考虑问题的长期特征的情况下,对任何一步都取最大值。你知道吗
相反,你需要从三角形的底部向上工作。在每个连接处,注意两条路径中的哪一条给出三角形底部的最大和,并将其记录为该节点的最佳结果。当你到达顶点时,你将得到下面两个元素中较大的一个。你知道吗
例如,给定三角形
您的算法将是贪婪的,并采用路径1-2-2-2;第二行中较低的选择
1
将该分支从短视逻辑中切断。你知道吗相反,您需要从底部开始构建总计,在每个节点上选择两条路径中的最佳路径:
万一这还不够清楚。。。 最下面的一行没有更多的选择;每个值都是它自己到达终点的最佳路径。对于上面的行,让我们从右向左,考虑每个值及其两个“子项”:
2
下面有两个值,1
和2
。显然,2
更好,因此从那里开始的最佳路径是2+2=4。 同样,1下面有2
和1
;同样,更好的路径是1+2,得到3。9
有1
和9
的子级;我们选择9+9=18。行现在显示为现在我们上移一行,把
2 1
的两个选项放在一起。2
有4
和3
;1
有3
和18
。再次在每种情况下取较高的值并加上节点值,我们得到2+4=6和1+18=19:最后,顶部节点选择较大的值19,沿着路径1-1-9-9总共得到20个。你知道吗
明白了吗?你知道吗
相关问题 更多 >
编程相关推荐