-4

プロジェクトのオイラー問題 18を解こうとしています。 http://projecteuler.net/problem=18 三角形の底から動作する python で貪欲なアルゴリズムを試してみました。次に、1 行上に移動して、貪欲なアルゴリズムで最大のルートを見つけ、最大のルートを接続しようとしますが、うまくいきません。問題の解決策を教えずに、私を正しい軌道に乗せるヒントはありますか.

ここに関数があります：

def greedy(i):
    if i%15==0:
        a=[(b[i-15],i-15),(b[i-14],i-14)]
        a=sorted(a)
        a=a[-1]
    else:
        a=[(b[i-15],i-15),(b[i-16],i-16),(b[i-14],i-14)]
        a=sorted(a)
        a=a[-1]
    return a

乾杯

4

1 に答える 1

4

動的計画法について聞いたことがありますか?

この問題を考えてみましょう。ルートを最高にするものは何ですか? 最後のステップと前のステップの間に関係はありますか? また、貪欲なアルゴリズムが正しい答えを与えないこの三角形を見てください。

      1
    2   3
  9   1   2
1   1   2   4
于 2012-04-23T13:48:42.740 に答える