Problem 67 「最大経路の和 その2」

以下の三角形の頂点から下まで移動するとき, その数値の合計の最大値は23になる.

3
7 4
2 4 6
8 5 9 3

この例では 3 + 7 + 4 + 9 = 23

100列の三角形を含んでいる15Kのテキストファイル triangle.txt (右クリックして, 『名前をつけてリンク先を保存』)の上から下まで最大合計を見つけよ.

:これは, Problem 18のずっと難しいバージョンです.
全部で2&sup{99}; 通りの組み合わせがあるので, この問題を解決するためにすべてのルートをためすことは可能でありません!
あなたが毎秒1兆本の(10&sup{12};)ルートをチェックすることができたとしても, 全てをチェックするために200億年以上かかるでしょう.
解決するための効率的なアルゴリズムがあります. ;o)


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS