广义双蛋之谜

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]; 
    } 
}