1

我正在用 Python 解决Project Euler 问题 #18。

我已经成功解决了那里给出的示例问题，但未能解决主要问题。但是代码是一样的。

代码是：

matrix = [('75', '0'),
    ('95', '64'),
    ('17', '47', '82'),
    ('18', '35', '87', '10'),
    ('20', '04', '82', '47', '65'),
    ('19', '01', '23', '75', '03', '34'),
    ('88', '02', '77', '73', '07', '63', '67'),
    ('99', '65', '04', '28', '06', '16', '70', '92'),
    ('41', '41', '26', '56', '83', '40', '80', '70', '33'),
    ('41', '48', '72', '33', '47', '32', '37', '16', '94', '29'),
    ('53', '71', '44', '65', '25', '43', '91', '52', '97', '51', '14'),
    ('70', '11', '33', '28', '77', '73', '17', '78', '39', '68', '17', '57'),
    ('91', '71', '52', '38', '17', '14', '91', '43', '58', '50', '27', '29', '48'),
    ('63', '66', '04', '68', '89', '53', '67', '30', '73', '16', '69', '87', '40', '31'),
    ('04', '62', '98', '27', '23', '09', '70', '98', '73', '93', '38', '53', '60', '04', '23')]

i = 0
j = 0
len = len(matrix )
sum = 0

for i in range(0,len):

    if matrix [i][j] > matrix [i][j + 1]:
        print matrix [i][j]
        sum = sum + int(matrix [i][j])
    else:
        print matrix [i][j+1]
        j = j + 1
        sum = sum + int(matrix [i][j])
print sum

谁能告诉我我错在哪里？

4

1 回答 1

8

抱歉，您使用的算法不正确。
您使用的称为贪心算法，但要使用的正确算法是动态编程。主要区别在于贪婪选择当前最佳选项作为选择，而动态编程枚举每个可能的选项并生成一系列选择。

有一个简单的案例，您的解决方案（贪婪）会失败：

0,  
1, 0,  
0, 0, 10

最好的结果是 10，但您的算法会给出 1。

自己想一想，然后尝试寻找有关动态编程的信息。Project Euler 是一个很棒的地方，当您提出解决方案时感觉非常棒。所以我暂时不会说太多。:)

更新：

但是问题：从下面三角形的顶部开始，移动到下面一行的“相邻数字”。我已经根据这个词制作了我的代码。抱歉打断你，但你能用这个词让我更清楚吗？

请注意，在给定的水平三角形上实际上2^(n-1)会有可能的路线。n并且在原始问题中maximum total意味着所有这些路线中的最大总数。
没有被授权者认为您的代码会在路线中找到最大值，因为您只会在任何步骤ALL中选择一个更好的选择。TWO

再次更新：

其实在这个问题中，既然n=15足够小，你也可以枚举所有2^(n-1)=16384可能的路线，总结每条路线的总值，最后在你得到的所有中得到一个最大值。然而，在Project Euler的第 67 题中，问题规模n增加到 100，并且不可能枚举所有2^(n-1)=633825300114114700748351602688路线。

顺便说一句，我已经发布了一个指向动态编程维基页面的链接，但我担心作为初学者阅读它会很复杂。对此感到抱歉。
不过别担心，只要谷歌动态编程教程，你就会看到很多有用的资源:)

于 2013-01-17T08:40:21.783 回答