廣義雙蛋之謎

Question

下面是問題描述：

假設我們想知道，在N層樓的樓層是安全的，從下降雞蛋，這將導致雞蛋着陸打破。我們做一些假設： 可以再次使用一隻可以摔倒的蛋。

• 破碎的蛋必須丟棄。
• 秋季的影響對於所有雞蛋都是一樣的。
• 如果一個雞蛋掉下來時破裂，那麼如果從較高的窗口掉下來，它會破裂。
• 如果一隻雞蛋存活下來，那麼它會在較短的秋天中倖存下來。
• 不排除一樓的窗戶打破雞蛋，也不排除N樓的窗戶不會導致雞蛋破損。

給定一個N層建築物和d蛋的供應，找出最小化（在最壞的情況下）確定破裂層所需的實驗液滴的數量的策略。

---

我已經看到並解決了2個雞蛋的問題，其中N = 100的答案是14。 我試圖理解從維基使用DP的一般化解決方案，但不能理解他們試圖做什麼。請告訴他們他們是如何到達DP以及它是如何工作的？

編輯：

的復發在this條爲可與d滴和e雞蛋待測試的最高FL OOR給定如下：

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

復發是好的，但我不能理解它是如何派生的？

這個解釋對我來說並不清楚......我只是想讓別人用更清晰的單詞向我解釋這種再發生。

Answer 1

（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] 

Answer 2

動態編程基礎的解決方案 - http://algohub.blogspot.in/2014/05/egg-drop-puzzle.html

我相信這是自explanatory..please隨時問，如果任何部分是不明確的..將竭誠爲講解

Answer 3

從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樓層。只有兩種可能的結果：

1. 它打破，所以問題遞歸來：x-1地板，n-1雞蛋，這反映了W(n-1,x-1)
2. 它不會破壞，所以問題遞歸來：k-x地板，n雞蛋，這反映了W(n,k-x)

既然問題需要最壞的情況下，我們必須選擇一個更大的保證最壞的情況下工作，這就是爲什麼我們W(n-1,x-1)和012之間增加一個最大。

此外，由於我們只是假設測試中x地板，x可以從1到k，在這種情況下，我們一定要選擇最小，以保證最小的實驗滴找出N，這就是爲什麼我們添加分鐘之間{max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k}

最後，因爲我們已經使用1下降x樓，所以方程必須添加1，這反映了方程的第一部分。

希望能解決您的難題:-)

Answer 4

這個問題可以通過以下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 

使用二叉搜索樹（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代表蛋的數量。

任何具有f個節點的BST，用上述類型的表示繪製並受到BST約束寬度= e（蛋數）是一種解決方案，但它可能不是最佳解決方案。

因此獲得最佳的解決方案是等效於獲得與經受約束最小高度BST節點的佈置：BST < = E

的寬度有關所有上述3種方法的詳細信息，請查看我博客在：3 approaches for solving generalized egg drop problem

Answer 5

這個問題是不是從哪個地板雞蛋應該下降，其即將最小化的數量下降。

• 假設，我們有N個雞蛋和K地板然後，
• 基本情況：
  • 當地板是1，那麼，MinNoOfDrops（N，1）= 1
  • 當雞蛋1的，MinNoOfDrops（1，K）= K
• Generailsed解決方案：
• MinNoOfDrops（N，K）= 1 + {分鐘最大（MinNoOfDrops（N - 1，X - 1），MinNoOfDrops（n，k-x））}，x = 1,2，...，K

---

動態規劃算法：

• 創建的（totalEggs + 1）X（totalFloors + 1）

• 基本案例DP表：當蛋0或1，然後設置爲第i層，表[0] [i] = 0;和表格[1] [i] = i

• 基礎案例：樓層爲零或一個，然後爲蛋j設置表[j] [0] = 0 和表[j] [1] = 1

• 迭代蛋i。從2至total_eggs從2

  • 迭代地板J即可total_floors
    • 集表[i] [j]從1 = INFINITY
    • 迭代地板ķ到j
    • 集maxDrop = 1 +最大（表[I-1] [K-1]，表[I] [JK]）
    • 如果表[i] [j]> maxDrop然後
      • 集表[i] [j] = maxDrop

---

public class EggDroppingPuzzle { 

    /** Not efficient **/ 
    public static int solveByRecursion(int totalEggs, int totalFloors) { 

     /** Base Case: When no floor **/ 
     if (totalFloors == 0) { 
      return 0; 
     } 

     /** Base case: When only one floor **/ 
     if (totalFloors == 1) { 
      return 1; 
     } 

     /** Base case: When only one eggs, then we have to try it from all floors **/ 
     if (totalEggs == 1) { 
      return totalFloors; 
     } 

     int minimumDrops = Integer.MAX_VALUE; 
     /** Now drop a egg from floor 1 to totalFloors **/ 
     for (int k = 1; k <= totalFloors; k++) { 

      /** When an egg breaks at kth floor **/ 
      int totalDropWhenEggBreaks = solveByRecursion(totalEggs - 1, k - 1); 

      /** When egg doesn't break at kth floor **/ 
      int totalDropWhenEggNotBreaks = solveByRecursion(totalEggs, totalFloors - k); 

      /** Worst between above conditions **/ 
      int maxDrop = Math.max(totalDropWhenEggBreaks, totalDropWhenEggNotBreaks); 


      /** Minimum drops for all floors **/ 
      if (minimumDrops > maxDrop) { 
       minimumDrops = maxDrop; 
      } 
     } 

     return minimumDrops + 1; 
    } 

    public static int solveByByDP(int totalEggs, int totalFloors) { 
     int[][] table = new int[totalEggs + 1][totalFloors + 1]; 

     /** Base Case: When egg is zero or one **/ 
     for (int i = 0; i < totalFloors + 1; i++) { 
      table[0][i] = 0; 
      table[1][i] = i; 
     } 

     /** Base case: Floor is zero or one **/ 
     for (int j = 0; j < totalEggs + 1; j++) { 
      table[j][0] = 0; 
      table[j][1] = 1; 
     } 

     /** For floor more than 1 and eggs are also more than 1 **/ 
     for (int i = 2; i < totalEggs + 1; i++) { 
      for (int j = 2; j < totalFloors + 1; j++) { 

       table[i][j] = Integer.MAX_VALUE; 
       for (int k = 1; k <= j; k++) { 

        /** When an egg breaks at kth floor **/ 
        int totalDropWhenEggBreaks = table[i - 1][k - 1]; 

        /** When egg doesn't break at kth floor **/ 
        int totalDropWhenEggNotBreaks = table[i][j - k]; 

        /** Worst between above conditions **/ 
        int maxDrop = 1 + Math.max(totalDropWhenEggBreaks, totalDropWhenEggNotBreaks); 

        /** Minimum drops for all floors **/ 
        if (maxDrop < table[i][j]) { 
         table[i][j] = maxDrop; 
        } 
       } 
      } 
     } 

     return table[totalEggs][totalFloors]; 
    } 
}