11

問題の説明は次のとおりです。

N 階建ての建物のどの階から卵を落とすのが安全で、どの階が着陸時に卵が壊れるかを知りたいとします。いくつかの仮定を立てます。落下しても生き残った卵は、再び使用できます。

  • 壊れた卵は捨てなければなりません。
  • 落下の影響はすべての卵で同じです。
  • 卵を落として割れたら、高い窓から落としても割れます。
  • 卵が落下を生き延びた場合、卵はより短い落下で生き残ります。
  • 1 階の窓が卵を割ることも、N 階の窓が卵を割らないことも除外されません。

N 階建ての建物と d 卵の供給が与えられた場合、ブレークフロアを決定するために必要な実験的落下回数を (最悪の場合) 最小化する戦略を見つけてください。

私は、N=100 に対して答えが 14 である 2 つの卵について、この問題を見て解決しました。DP を使用して wiki から一般化されたソリューションを理解しようとしましたが、彼らが何をしようとしているのか理解できませんでした。彼らがどのようにして DP にたどり着き、どのように機能しているか教えてください。

編集 ：

d ドロップと e 卵でテストできる最高階について、この記事に記載されている再現性は次のとおりです。

f[d,e] = f[d-1,e] + f[d-1,e-1] + 1

再発は問題ありませんが、それがどのように導出されるのか理解できませんか?

説明は私には明確ではありません....誰かがこの再発をもっと明確な言葉で説明してほしい.

4

5 に答える 5

12

（1）最初の一滴が卵を割る場合を考えてみましょう。次に、ブレークフロアが最大でf [d-1、e-1]である場合にのみ、ブレークフロアを決定できます。したがって、f [d-1、e-1] + 1より高く開始することはできません（もちろん、低く開始するべきではありません）。

（2）最初のドロップで卵が壊れない場合は、f [d-1、e]の場合、1階ではなく、最初のドロップ+1のフロアから開始します。

したがって、あなたができる最善のことは、床f [d-1、e-1] + 1で卵を落とし始めることです（（1）のため）、そしてあなたはf [d-1、e]階まで上がることができますそれより（（2）のため）。それは

f[d, e] = f[d-1, e-1] + 1 + f[d-1, e]
于 2012-04-16T21:21:50.223 に答える
10

Wiki Egg Dropping puzzleから、状態伝達方程式は次のようになることがわかります。

W(n,k) = 1 + min{ max(W(n − 1, x − 1), W(n,k − x)) } , x = 1, 2, ..., k

W(n,1)=1, W(1,k)=k

n= 利用可能な試験卵の数

k= まだテストされていない (連続した) フロアの数

以下は私の理解です。

k床、卵があります。床nでテストするために卵を使用すると仮定しますx。考えられる結果は 2 つだけです。

  1. それは壊れるので、問題は再帰的に次のようになります：x-1床、n-1卵、それはに反映されますW(n-1,x-1)
  2. それは壊れないので、問題は再帰的に発生します:k-x床、n卵、に反映されます。W(n,k-x)

この問題には最悪のケースが必要なので、最悪のケースが確実に機能するように、より大きなものを選択する必要があります。そのため、 ～ の間に最大値を追加しW(n-1,x-1)ますW(n,k-x)。

xさらに、フロアでのテストはからまでx可能であると想定したので、この状況では、最小の実験的ドロップを確認するために最小値を選択する必要があります。そのため、間に最小値を追加し ます。1kN{max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k}

最後に、1ドロップ イン x フロアを使用したため、方程式は を追加する必要があり、これは方程式1の最初の部分に反映されます。

それがあなたのパズルを解決することを願っています:-)

于 2014-08-11T09:01:36.203 に答える
0

この問題は、次の3つのアプローチで解決できます（私が知っている）：

  1. 動的計画法
  2. 二分探索木を使った解法
  3. 与えられた数の卵と与えられた滴数でテストまたはカバーできる床の最大数の直接的な数式を得ることによる解決策

最初に、後で行われる分析で使用されるいくつかの記号を定義しましょう。

e = number of eggs
f = number of floors in building
n = number of egg drops 
Fmax(e, n) = maximum number of floors that can be tested or covered with e eggs and n drops

動的計画法アプローチの核心は、次の Fmax の再帰式にあります。

Fmax(e, n) = 1 + Fmax(e-1, n-1) + fmax(e, n-1)

そして、Fmax の直接的な数式を取得するための核心は、Fmax の次の再帰的な数式にあります。

Fmax(e, n) = { ∑Fmax(e-1,i) for i = 1 to n } - Fmax(e-1, n) + n

この問題には、Binary Search Tree (BST) を使用した代替ソリューションも可能です。分析を容易にするために、次のように少し変更して BST を描画します。

1.    If egg breaks then child node is drawn on left down side
2.    If egg does not break then child node is drawn straight down side

上記の種類の表現で BST を描画すると、BST の幅は卵の数を表します。

上記の種類の表現で描画され、BST <= e (卵の数) の制約幅が適用される f 個のノードを持つ任意の BST は解ですが、最適な解ではない可能性があります。

したがって、最適な解を取得することは、BST のノードの配置を最小の高さの制約の下で取得することと同じです: BST の幅 <= e

上記の 3 つのアプローチの詳細については、次のブログを参照してください。

于 2016-12-31T12:46:07.130 に答える