4

私は Project Euler の問題に取り組んできましたが、ほとんどの場合、うまくやっています。問題18ですが、本当に困惑しました。

木のてっぺんから始めて、最大の合計につながるパスを見つけることになっています

      3
    7   4
  2   4   6
8   5   9   3

この場合、24 の可能なパス、つまり 4 つがあります。最適なパスは3 -> 7 -> 4 -> 9で、合計すると 23 になります。

例を複製して問題を解決しようとしました。

array = [[3],[7,4],[2,4,6],[8,5,9,3]]
array.each_slice(1){|s|p s}                          => This prints the tree

まれに正しい回答が得られましたが、実際には正当ではありません。

sum = []
array.each{|a|sum.push(a.sample)}
return sum

この方法は、基本的にはランダムなパスを選択するだけであり、この簡単な例でも、24 分の 1 の確率で正しいパスが得られるだけです。

私は次のようなことを試しました

level_two = []
level_three = []
for i in 0..array.length-1
  for j in 0..array[1].length-1
    level_two.push([array[0], array[1][i])        => Now level 2 has 2 paths - [3,7] & [3,4]
    for k in 0..array[2].length-1
      level_three.push([level_two[0],array[2][k], [level_two[1], array[2][k])
    end
  end
end

しかし、この時点では、使用している変数を追跡することさえできません。

each_cons、combination、zip を試しましたが、どれもうまくいきませんでした。

この問題を解決するための戦略を知っている人はいますか?

編集:これは問題に対する答えではなく、単に例に対する答えです。次に、その設計パターンを主な問題に適用します。

4

4 に答える 4

2

この問題は、再帰の完璧な使用例です。用語についてT[3][0]は、0 から数えて 3 行目の 0 番目の要素 (この例では 8) であるとしましょう。

木のてっぺんから始めて、最大の合計に至る経路は何ですか? まず、これを少し言い換えてみましょう: 最大合計が から始まるパスは何T[0][0]ですか? それはプラスまたはT[0][0]で始まるパスになります（どちらか大きい方のパス）。パス自体を見つけることは、最大の和を見つけることに付随するので、そこだけに焦点を当てます。T[1][0]T[1][1]

S[x][y]で始まるパスの最大和だとしましょうT[x][y]。次に、以前の観察から、

S[x][y] = T[x][y] + MAX(S[x + 1][y], S[x + 1][y + 1])

xツリーの最後の行でない限り。Rその場合、ツリーの最後の行にしましょう

S[R][y] = T[R][y]

Ruby では、次のように関数を記述できます。

def largest_sum_path(tree, x = 0, y = 0)
  path = [tree[x][y]]

  return path if x == tree.length - 1

  left  = largest_sum_path(tree, x + 1, y)
  right = largest_sum_path(tree, x + 1, y + 1)

  return path.concat([left, right].max_by { |p| p.reduce(:+) })
end

ただし、このアプローチは大きなツリーでは非常に遅くなると思います。どのように最適化できるかは、あなたにお任せします。

于 2014-11-12T18:06:38.333 に答える
1

最後の行から開始します。これを、連続する各ペアの最大値からなる行に置き換えます。つまり、8 5 9 3-> 8 9 9. これらの値をその上の行に追加します ( 2 4 6 -> 10 13 15)。最初の行まで繰り返します。(10 13 15 -> 13 15、7 4 -> 20 19 -> 20; 3 -> 23.

于 2014-11-12T19:07:33.563 に答える