1

Python でProject Euler Problem #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

申し訳ありませんが、間違ったアルゴリズムを使用しています。使用しているものは貪欲アルゴリズム
と呼ばれますが、使用する正しいアルゴリズムはDynamic Programmingです。主な違いは、動的プログラミングがすべての可能なオプションを列挙し、一連の選択肢を生成するのに対し、貪欲は現在の最良のオプションを選択肢として選択することです。

あなたのソリューション（貪欲）が失敗する単純なケースがあります：

0,  
1, 0,  
0, 0, 10

最良の結果は 10 ですが、アルゴリズムは代わりに 1 を返します。

少し自分で考えてから、動的計画法に関する情報を探してみてください。Project Euler は素晴らしい場所であり、解決策を思いついたときの気分は最高です。そのため、今は多くを語ることはしません。:)

更新しました：

ただし、質問: 下の三角形の上部から始めて、下の行の「隣接する数字」に移動します。私はこの言葉に従って自分のコードを作りました。中断して申し訳ありませんが、この言葉で私をより明確にすることができますか?

与えられたレベル三角形には、実際に2^(n-1)可能なルートがあることに注意してください。nそして、元の問題maximum totalでは、これらすべてのルートの最大合計を意味します。任意のステップでより良いルートのみを選択する
ため、コードがルートの中で最大のものを見つけるという被付与者はいません。ALLTWO

再度更新:

実際、この問題でn=15は十分に小さいので、すべての2^(n-1)=16384可能なルートを列挙し、各ルートの合計値を要約し、最終的に取得したすべての中で最大の合計を取得することもできます。ただし、Project Eulerの問題 67 では、問題のサイズが 100 に増え、すべてのルート nを列挙することはできません。2^(n-1)=633825300114114700748351602688

ところで、動的プログラミングのwikiページへのリンクを貼っておきましたが、初心者として読むには複雑すぎるのではないかと思います。そのために残念。
でも心配はいりません。Google動的プログラミングのチュートリアルだけで、役立つリソースがたくさんあります :)

于 2013-01-17T08:40:21.783 に答える