11

这是问题描述：

假设我们想知道 N 层建筑中的哪些楼层可以安全地掉落鸡蛋，哪些楼层会导致鸡蛋在落地时破裂。我们做了一些假设：一个在跌倒中幸存下来的鸡蛋可以再次使用。

  • 必须丢弃破损的鸡蛋。
  • 跌倒对所有鸡蛋的影响都是一样的。
  • 如果一个鸡蛋在掉落时会破裂，那么如果从更高的窗户掉落它就会破裂。
  • 如果一个鸡蛋在坠落中幸存下来，那么它会在较短的坠落中幸存下来。
  • 不排除一楼窗户打碎鸡蛋，也不排除N楼窗户不打碎鸡蛋。

给定一栋 N 层建筑和 d 个鸡蛋的供应，找出最小化（在最坏情况下）确定起床所需的实验下降次数的策略。

我已经看到并解决了 2 个鸡蛋的这个问题，其中 N=100 的答案是 14。我试图使用 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 谜题中，我们知道状态转移方程为：

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)和之间添加最大值的原因W(n,k-x)。

此外，由于我们刚刚假设在xfloor 中进行测试，x可以从1to k，在这种情况下，我们肯定需要选择最小值以确保 min 实验下降来找出N，这就是为什么我们在之间添加一个 min {max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k}

最后，由于我们使用1了 x floor 的下降，所以方程必须添加1，这反映到方程的第一部分。

希望能解决你的难题:-)

于 2014-08-11T09:01:36.203 回答
0

此处提供基于动态编程的解决方案 - http://algohub.blogspot.in/2014/05/egg-drop-puzzle.html

我相信这是不言自明的..如果任何部分不清楚，请随时询问..将很乐意解释

于 2014-05-08T06:28:05.663 回答
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

对于这个问题，使用二叉搜索树 (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 种方法

于 2016-12-31T12:46:07.130 回答
0

这个问题不在于应该从哪个地板上掉下鸡蛋，而是要尽量减少掉下的次数。

  • 假设，那么我们有 n 个鸡蛋和 k 个楼层，
  • 基本情况：
    • 那么当 floor 为 1 时，MinNoOfDrops(n, 1)=1
    • 而当egg为1时，MinNoOfDrops(1, k)=k
  • 通用解决方案：
  • MinNoOfDrops(n, k) = 1 + min{ max(MinNoOfDrops(n - 1, x - 1),
    MinNoOfDrops(n,k - x)) } , x = 1, 2, ..., k

动态规划算法：

  • 创建 (totalEggs + 1) X (totalFloors + 1) 的 dp 表

  • 基本情况：当egg为0或1时，设置为第i层，table[0][i] = 0；和表[1][i] = i

  • 基本情况：地板为零或一，然后设置为鸡蛋 j，table[j][0] = 0 和 table[j][1] = 1

  • 将鸡蛋 i 从 2 迭代到 total_eggs

    • 将层 j 从 2 迭代到 total_floors
      • 设置表[i][j] = INFINITY
      • 将楼层 k 从 1 迭代到 j
      • 设置 maxDrop = 1 + max(table[i-1][k-1], table[i][jk])
      • 如果 table[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];
    }
}
于 2017-01-08T07:31:53.540 回答