算法设计：扔鸡蛋问题 – 动态规划

2021年3月11日17:50:37 发表评论 640 次浏览

本文概述

扔鸡蛋问题

以下是对这个著名难题的实例的描述, 该难题涉及n = 2个鸡蛋和k = 36层的建筑物。

假设我们希望知道36层建筑物中的哪个楼层可以安全地放下鸡蛋, 并且哪些会导致鸡蛋在着陆时破裂。我们做一些假设：

…..跌落下来的鸡蛋可以再次使用。

…..破蛋必须丢弃。

…..跌落对所有鸡蛋的影响都是相同的。

…..如果鸡蛋掉落时破裂, 那么如果从较高的地板掉落, 鸡蛋也会破裂。

…..如果鸡蛋在跌落中幸存下来, 那么它在较短的跌落中幸存下来。

…..不能排除一楼的窗户破鸡蛋, 也不可以排除第36层的窗户不会破鸡蛋。

如果只有一个鸡蛋可用, 并且我们希望确保获得正确的结果, 则只能以一种方式进行实验。从一楼的窗户放鸡蛋；如果它仍然存在, 请将其从第二层窗口中放下。继续向上直到破裂。在最坏的情况下, 此方法可能需要丢弃36次。假设有2个鸡蛋。保证在所有情况下都能正常工作的最少的排卵次数是多少？

问题实际上不是找到关键的最低限度, 而只是确定应该从中跌落鸡蛋的最低限度, 以使试验的总数最小化。

资源：动态编程维基

推荐：请在"实践首先, 在继续解决方案之前。

方法1:递归。

在这篇文章中, 我们将讨论解决" n"个鸡蛋和" k"个地板的一般问题的解决方案。解决方案是尝试从每个楼层(从1到k)投下一个鸡蛋, 并递归计算最坏情况下所需的最小投掷次数。在最坏的情况下提供最小值的最低要求将成为解决方案的一部分。

在以下解决方案中, 我们返回最坏情况下的最少试验次数；这些解决方案可以轻松修改, 以打印每个试验的楼层编号。

最坏情况的含义：最坏情况使用户有底限的保证。例如-如果我们有'1'鸡蛋和'k'地板, 我们将从一楼开始放鸡蛋, 直到假设鸡蛋在'kth'地板上破裂为止, 因此为我们提供保证的尝试次数为'k' 。

1)最佳子结构：

当我们从地板x上放一个鸡蛋时, 可能有两种情况(1)鸡蛋破裂(2)鸡蛋没有破裂。

  1. 如果鸡蛋从'xth'地板掉落后破裂, 那么我们只需要检查剩余鸡蛋数量低于'x'的地板, 因为某些地板应该存在低于'x'且鸡蛋不会破裂的地板；因此问题减少到x-1层和n-1个鸡蛋。
  2. 如果鸡蛋从'xth'地板掉下来后仍未破裂, 则我们只需要检查高于'x'的地板即可；因此问题减少到" k-x"层和n个鸡蛋。

由于我们需要尽量减少最坏的情况下, 我们最多只能考虑两种情况。我们考虑每个楼层的上述两种情况中的最大值, 并选择产生最少试验次数的楼层。

k ==>楼层数n ==>鸡蛋数eggDrop(n, k)==>在最坏情况下找到关键楼层所需的最少试验次数。 eggDrop(n, k)= 1 + min {max(eggDrop(n – 1, x – 1), eggDrop(n, k – x))), 其中x在{1, 2, …, k}}中最坏的情况：例如：让" 2"个鸡蛋和" 2"个地板, 然后-：如果我们尝试从" 1st"地板扔球：最坏情况下的尝试次数= 1 + max(0, 1)0 =>如果鸡蛋从第一层破损, 然后是阈值层(最好的情况)。 1 =>如果鸡蛋没有从第一层破掉, 我们现在将有"​​ 2"个鸡蛋和一层要测试的鸡蛋, 其答案将为" 1"。(最坏情况的可能性)我们考虑了最坏情况的可能性, 因此1 + max(0, 1)= 2如果我们尝试从'第二层'投掷：最坏情况下的尝试次数= 1 + max(1, 0)1 =>如果鸡蛋从第二层破损, 那么我们将有1个鸡蛋在1楼找到阈值地板。(最坏情况)0 =>如果鸡蛋没有从第二层摔破, 则为阈值地板。(最好的情况)我们考虑最坏情况的可能性, 因此1 + max(1, 0) = 2。最终答案是分钟(第1楼, 第2楼, 第3楼….., k楼), 所以这里的答案是" 2"。

下面是上述方法的实现：

C ++

#include <bits/stdc++.h>
using namespace std;
  
// A utility function to get
// maximum of two integers
int max( int a, int b)
{
     return (a > b) ? a : b;
}
  
// Function to get minimum
// number of trials needed in worst
// case with n eggs and k floors
int eggDrop( int n, int k)
{
     // If there are no floors, // then no trials needed.
     // OR if there is one floor, // one trial needed.
     if (k == 1 || k == 0)
         return k;
  
     // We need k trials for one
     // egg and k floors
     if (n == 1)
         return k;
  
     int min = INT_MAX, x, res;
  
     // Consider all droppings from
     // 1st floor to kth floor and
     // return the minimum of these
     // values plus 1.
     for (x = 1; x <= k; x++) {
         res = max(
             eggDrop(n - 1, x - 1), eggDrop(n, k - x));
         if (res < min)
             min = res;
     }
  
     return min + 1;
}
  
// Driver program to test
// to pront printDups
int main()
{
     int n = 2, k = 10;
     cout << "Minimum number of trials "
             "in worst case with "
          << n << " eggs and " << k
          << " floors is "
          << eggDrop(n, k) << endl;
     return 0;
}
  
// This code is contributed
// by Akanksha Rai

C

#include <limits.h>
#include <stdio.h>
  
// A utility function to get
// maximum of two integers
int max( int a, int b)
{
     return (a > b) ? a : b;
}
  
/* Function to get minimum number of 
  trials needed in worst case with n eggs
  and k floors */
int eggDrop( int n, int k)
{
     // If there are no floors, then no
     // trials needed. OR if there is
     // one floor, one trial needed.
     if (k == 1 || k == 0)
         return k;
  
     // We need k trials for one egg and
     // k floors
     if (n == 1)
         return k;
  
     int min = INT_MAX, x, res;
  
     // Consider all droppings from 1st
     // floor to kth floor and
     // return the minimum of these values
     // plus 1.
     for (x = 1; x <= k; x++) {
         res = max(
             eggDrop(n - 1, x - 1), eggDrop(n, k - x));
         if (res < min)
             min = res;
     }
  
     return min + 1;
}
  
/* Driver program to test to pront printDups*/
int main()
{
     int n = 2, k = 10;
     printf ( "nMinimum number of trials in "
            "worst case with %d eggs and "
            "%d floors is %d \n" , n, k, eggDrop(n, k));
     return 0;
}

Java

public class GFG {
  
     /* Function to get minimum number of 
     trials needed in worst case with n 
     eggs and k floors */
     static int eggDrop( int n, int k)
     {
         // If there are no floors, then
         // no trials needed. OR if there
         // is one floor, one trial needed.
         if (k == 1 || k == 0 )
             return k;
  
         // We need k trials for one egg
         // and k floors
         if (n == 1 )
             return k;
  
         int min = Integer.MAX_VALUE;
         int x, res;
  
         // Consider all droppings from
         // 1st floor to kth floor and
         // return the minimum of these
         // values plus 1.
         for (x = 1 ; x <= k; x++) {
             res = Math.max(eggDrop(n - 1 , x - 1 ), eggDrop(n, k - x));
             if (res < min)
                 min = res;
         }
  
         return min + 1 ;
     }
  
     // Driver code
     public static void main(String args[])
     {
         int n = 2 , k = 10 ;
         System.out.print( "Minimum number of "
                          + "trials in worst case with "
                          + n + " eggs and " + k
                          + " floors is " + eggDrop(n, k));
     }
     // This code is contributed by Ryuga.
}

Python 3

import sys 
  
# Function to get minimum number of trials 
# needed in worst case with n eggs and k floors 
def eggDrop(n, k):
  
     # If there are no floors, then no trials
     # needed. OR if there is one floor, one
     # trial needed.
     if (k = = 1 or k = = 0 ):
         return k
  
     # We need k trials for one egg 
     # and k floors
     if (n = = 1 ):
         return k
  
     min = sys.maxsize
  
     # Consider all droppings from 1st 
     # floor to kth floor and return 
     # the minimum of these values plus 1.
     for x in range ( 1 , k + 1 ):
  
         res = max (eggDrop(n - 1 , x - 1 ), eggDrop(n, k - x))
         if (res < min ):
             min = res
  
     return min + 1
  
# Driver Code
if __name__ = = "__main__" :
  
     n = 2
     k = 10
     print ( "Minimum number of trials in worst case with" , n, "eggs and" , k, "floors is" , eggDrop(n, k))
  
# This code is contributed by ita_c

C#

using System;
  
class GFG {
  
     /* Function to get minimum number of 
     trials needed in worst case with n 
     eggs and k floors */
     static int eggDrop( int n, int k)
     {
         // If there are no floors, then
         // no trials needed. OR if there
         // is one floor, one trial needed.
         if (k == 1 || k == 0)
             return k;
  
         // We need k trials for one egg
         // and k floors
         if (n == 1)
             return k;
  
         int min = int .MaxValue;
         int x, res;
  
         // Consider all droppings from
         // 1st floor to kth floor and
         // return the minimum of these
         // values plus 1.
         for (x = 1; x <= k; x++) {
             res = Math.Max(eggDrop(n - 1, x - 1), eggDrop(n, k - x));
             if (res < min)
                 min = res;
         }
  
         return min + 1;
     }
  
     // Driver code
     static void Main()
     {
         int n = 2, k = 10;
         Console.Write( "Minimum number of "
                       + "trials in worst case with "
                       + n + " eggs and " + k
                       + " floors is " + eggDrop(n, k));
     }
}
  
// This code is contributed by Sam007.

输出如下：

Minimum number of trials in worst 
case with 2 eggs and 10 floors is 4

应该注意的是, 上述函数一次又一次地计算相同的子问题。请参阅下面的部分递归树, E(2, 2)被评估两次。绘制完整的递归树时, 即使对于较小的n和k值, 也会有许多重复的子问题。

E(2, 4)
                           |                      
          ------------------------------------- 
          |             |           |         |   
          |             |           |         |       
      x=1/          x=2/      x=3/     x=4/ 
        /             /         ....      ....
       /             /    
 E(1, 0)  E(2, 3)     E(1, 1)  E(2, 2)
          /  /...         /  
      x=1/                 .....
        /    
     E(1, 0)  E(2, 2)
            /   
            ......

Partial recursion tree for 2 eggs and 4 floors.

复杂度分析：

  • 时间复杂度：由于存在子问题重叠的情况, 因此时间复杂度是指数级的。
  • 辅助空间：O(1)。由于没有使用任何数据结构来存储值。

由于再次调用了相同的问题, 因此此问题具有"重叠子问题"属性。因此, Egg Dropping Puzzle具有两种属性(请参阅这个和这个)的动态编程问题。像其他典型的动态编程(DP)问题, 可以通过自下而上的方式构造一个临时数组eggFloor [] []来避免相同子问题的重新计算。

方法2:动态编程。

在这种方法中, 我们致力于上述相同的想法忽略了一次又一次地计算子问题答案的情况。。方法是制作一个表, 该表将存储子问题的结果, 以便解决子问题, 只需要从该表中查找即可恒定时间, 之前指数时间.

正式用于填充DP [i] [j]状态, 其中" i"是鸡蛋数, " j"是楼层数：

我们必须从" 1"到" j"遍历每个楼层" x", 并找出最小值：(1 + max(DP [i-1] [j-1], DP [i] [j-x]))。

该模拟将使事情变得清晰：

i =>鸡蛋数j =>楼层数查找最大数量让我们为以下情况填写表格：楼层='4'鸡蛋='2'1 2 3 4 1 2 3 4 => 1 1 2 2 3 => 2对于'egg-1', 每种情况都是基本情况, 因此尝试次数等于下限次数。对于" egg-2", 对于1楼(基本情况), 将尝试" 1"。对于2楼=>进入1楼1 + max(0, DP [1] [1])进入2楼1 + max(DP [1] [1], 0)DP [2] [2] = min( 1 + max(0, DP [1] [1]), 1 + max(DP [1] [1], 0))对于floor-3 =>进入1楼1 + max(0, DP [2] [ 2])取2楼1 + max(DP [1] [1], DP [2] [1])取3楼1 + max(0, DP [2] [2])DP [2] [3] =最小值("所有三个楼层")= 2对于4楼=>进入1楼1 + max(0, DP [2] [3])进入2楼1 + max(DP [1] [1], DP [2] [2])进入3楼1 + max(DP [1] [2], DP [2] [1])进入4楼1 + max(0, DP [2] [3])DP [2 ] [4] =分钟("所有四个楼层")= 3

C ++

// A Dynamic Programming based for
// the Egg Dropping Puzzle
#include <limits.h>
#include <stdio.h>
  
// A utility function to get
// maximum of two integers
int max( int a, int b)
{
     return (a > b) ? a : b;
}
  
/* Function to get minimum 
number of trials needed in worst 
case with n eggs and k floors */
int eggDrop( int n, int k)
{
     /* A 2D table where entery 
     eggFloor[i][j] will represent 
     minimum number of trials needed for
     i eggs and j floors. */
     int eggFloor[n + 1][k + 1];
     int res;
     int i, j, x;
  
     // We need one trial for one floor and 0
     // trials for 0 floors
     for (i = 1; i <= n; i++) {
         eggFloor[i][1] = 1;
         eggFloor[i][0] = 0;
     }
  
     // We always need j trials for one egg
     // and j floors.
     for (j = 1; j <= k; j++)
         eggFloor[1][j] = j;
  
     // Fill rest of the entries in table using
     // optimal substructure property
     for (i = 2; i <= n; i++) {
         for (j = 2; j <= k; j++) {
             eggFloor[i][j] = INT_MAX;
             for (x = 1; x <= j; x++) {
                 res = 1 + max(
                               eggFloor[i - 1][x - 1], eggFloor[i][j - x]);
                 if (res < eggFloor[i][j])
                     eggFloor[i][j] = res;
             }
         }
     }
  
     // eggFloor[n][k] holds the result
     return eggFloor[n][k];
}
  
/* Driver program to test to pront printDups*/
int main()
{
     int n = 2, k = 36;
     printf ( "\nMinimum number of trials "
            "in worst case with %d eggs and "
            "%d floors is %d \n" , n, k, eggDrop(n, k));
     return 0;
}

Java

// A Dynamic Programming based Java
// Program for the Egg Dropping Puzzle
class EggDrop {
  
     // A utility function to get
     // maximum of two integers
     static int max( int a, int b)
     {
         return (a > b) ? a : b;
     }
  
     /* Function to get minimum number 
  of trials needed in worst
     case with n eggs and k floors */
     static int eggDrop( int n, int k)
     {
         /* A 2D table where entery eggFloor[i][j] 
  will represent minimum number of trials 
needed for i eggs and j floors. */
         int eggFloor[][] = new int [n + 1 ][k + 1 ];
         int res;
         int i, j, x;
  
         // We need one trial for one floor and
         // 0 trials for 0 floors
         for (i = 1 ; i <= n; i++) {
             eggFloor[i][ 1 ] = 1 ;
             eggFloor[i][ 0 ] = 0 ;
         }
  
         // We always need j trials for one egg
         // and j floors.
         for (j = 1 ; j <= k; j++)
             eggFloor[ 1 ][j] = j;
  
         // Fill rest of the entries in table using
         // optimal substructure property
         for (i = 2 ; i <= n; i++) {
             for (j = 2 ; j <= k; j++) {
                 eggFloor[i][j] = Integer.MAX_VALUE;
                 for (x = 1 ; x <= j; x++) {
                     res = 1 + max(
                                   eggFloor[i - 1 ][x - 1 ], eggFloor[i][j - x]);
                     if (res < eggFloor[i][j])
                         eggFloor[i][j] = res;
                 }
             }
         }
  
         // eggFloor[n][k] holds the result
         return eggFloor[n][k];
     }
  
     /* Driver program to test to pront printDups*/
     public static void main(String args[])
     {
         int n = 2 , k = 10 ;
         System.out.println( "Minimum number of trials in worst"
                            + " case with "
                            + n + "  eggs and "
                            + k + " floors is " + eggDrop(n, k));
     }
}
/*This code is contributed by Rajat Mishra*/

python

# A Dynamic Programming based Python Program for the Egg Dropping Puzzle
INT_MAX = 32767
  
# Function to get minimum number of trials needed in worst
# case with n eggs and k floors
def eggDrop(n, k):
     # A 2D table where entery eggFloor[i][j] will represent minimum
     # number of trials needed for i eggs and j floors.
     eggFloor = [[ 0 for x in range (k + 1 )] for x in range (n + 1 )]
  
     # We need one trial for one floor and0 trials for 0 floors
     for i in range ( 1 , n + 1 ):
         eggFloor[i][ 1 ] = 1
         eggFloor[i][ 0 ] = 0
  
     # We always need j trials for one egg and j floors.
     for j in range ( 1 , k + 1 ):
         eggFloor[ 1 ][j] = j
  
     # Fill rest of the entries in table using optimal substructure
     # property
     for i in range ( 2 , n + 1 ):
         for j in range ( 2 , k + 1 ):
             eggFloor[i][j] = INT_MAX
             for x in range ( 1 , j + 1 ):
                 res = 1 + max (eggFloor[i - 1 ][x - 1 ], eggFloor[i][j - x])
                 if res < eggFloor[i][j]:
                     eggFloor[i][j] = res
  
     # eggFloor[n][k] holds the result
     return eggFloor[n][k]
  
# Driver program to test to pront printDups
n = 2
k = 36
print ( "Minimum number of trials in worst case with" + str (n) + "eggs and " 
        + str (k) + " floors is " + str (eggDrop(n, k)))
  
# This code is contributed by Bhavya Jain

C#

// A Dynamic Programming based C# Program
// for the Egg Dropping Puzzle
using System;
  
class GFG {
  
     // A utility function to get maximum of
     // two integers
     static int max( int a, int b)
     {
         return (a > b) ? a : b;
     }
  
     /* Function to get minimum number of 
     trials needed in worst case with n
     eggs and k floors */
     static int eggDrop( int n, int k)
     {
  
         /* A 2D table where entery eggFloor[i][j]
         will represent minimum number of trials
         needed for i eggs and j floors. */
         int [, ] eggFloor = new int [n + 1, k + 1];
         int res;
         int i, j, x;
  
         // We need one trial for one floor and0
         // trials for 0 floors
         for (i = 1; i <= n; i++) {
             eggFloor[i, 1] = 1;
             eggFloor[i, 0] = 0;
         }
  
         // We always need j trials for one egg
         // and j floors.
         for (j = 1; j <= k; j++)
             eggFloor[1, j] = j;
  
         // Fill rest of the entries in table
         // using optimal substructure property
         for (i = 2; i <= n; i++) {
             for (j = 2; j <= k; j++) {
                 eggFloor[i, j] = int .MaxValue;
                 for (x = 1; x <= j; x++) {
                     res = 1 + max(eggFloor[i - 1, x - 1], eggFloor[i, j - x]);
                     if (res < eggFloor[i, j])
                         eggFloor[i, j] = res;
                 }
             }
         }
  
         // eggFloor[n][k] holds the result
         return eggFloor[n, k];
     }
  
     // Driver function
     public static void Main()
     {
         int n = 2, k = 36;
         Console.WriteLine( "Minimum number of trials "
                           + "in worst case with " + n + " eggs and "
                           + k + "floors is " + eggDrop(n, k));
     }
}
  
// This code is contributed by Sam007.

的PHP

<?php
// A Dynamic Programming based PHP 
// Program for the Egg Dropping Puzzle
  
/* Function to get minimum number
    of trials needed in worst
    case with n eggs and k floors */
function eggDrop( $n , $k )
{
      
     /* A 2D table where entery eggFloor[i][j]
        will represent minimum number of 
        trials needed for i eggs and j floors. */
     $eggFloor = array ( array ());;
      
     // We need one trial for one 
     // floor and0 trials for 0 floors
     for ( $i = 1; $i <= $n ; $i ++)
     {
         $eggFloor [ $i ][1] = 1;
         $eggFloor [ $i ][0] = 0;
     }
  
     // We always need j trials
     // for one egg and j floors.
     for ( $j = 1; $j <= $k ; $j ++)
         $eggFloor [1][ $j ] = $j ;
  
     // Fill rest of the entries in 
     // table using optimal substructure
     // property
     for ( $i = 2; $i <= $n ; $i ++)
     {
         for ( $j = 2; $j <= $k ; $j ++)
         {
             $eggFloor [ $i ][ $j ] = 999999;
             for ( $x = 1; $x <= $j ; $x ++)
             {
                 $res = 1 + max( $eggFloor [ $i - 1][ $x - 1], $eggFloor [ $i ][ $j - $x ]);
                 if ( $res < $eggFloor [ $i ][ $j ])
                     $eggFloor [ $i ][ $j ] = $res ;
             }
         }
     }
  
     // eggFloor[n][k] holds the result
     return $eggFloor [ $n ][ $k ];
}
  
     // Driver Code
     $n = 2;
     $k = 36;
     echo "Minimum number of trials in worst case with " . $n . " eggs and "
                                     . $k . " floors is " .eggDrop( $n , $k ) ;
                                      
// This code is contributed by Sam007
?>

输出：

Minimum number of trials in worst 
case with 2 eggs and 36 floors is 8

复杂度分析：

  • 时间复杂度：O(n * k ^ 2)。
    其中" n"是鸡蛋的数量, " k"是楼层的数量, 因为我们对每个鸡蛋使用嵌套的循环" k ^ 2"次
  • 辅助空间：O(n * k)。
    由于大小为" n * k"的二维数组用于存储元素。

作为练习, 你可以尝试修改上述DP解决方案以打印所有中间楼层(用于最小试验解决方案的楼层)。

更高效的解决方案:鸡蛋掉落之谜(二项式系数和二元搜索解决方案)

2个鸡蛋和K层鸡蛋丢拼图

2个鸡蛋和100个地板拼图

参考文献：

http://archive.ite.journal.informs.org/Vol4No1/Sniedovich/index.php

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: