动态规划法（六）鸡蛋掉落问题（一）（egg dropping problem）

﹏ヽ暗。殇╰゛Y 2022-05-23 08:11 204阅读 0赞

继续讲故事~~  
  这天，丁丁正走在路上，欣赏着路边迷人的城市风景，突然发现前面的大楼前围了一波吃瓜群众。他好奇地凑上前去，想一探究竟，看看到底发生了什么事情。  
  原来本市的一位小有名气的科学家正在这幢大楼进行一个实验：某种材料的防护性能。他在大楼的底下铺了一层这种防护材料，想拿鸡蛋做实验，将鸡蛋从楼层掉下，看看鸡蛋从哪一层掉下去会摔碎，以此测试该材料的防护性能。这就是著名的鸡蛋掉落问题（egg dropping problem），即给定N个鸡蛋和k层楼，试问至少需要几次才能确定鸡蛋从哪一层楼掉下去恰好摔碎。  
  一听到这个问题，他顿时感觉无从下手，没有丝毫的头绪。但他尝试着先从最简单的情形入手：

*  若鸡蛋数N=0或者楼层数为0，则尝试0次即可。
 *  若鸡蛋数N=1， 对于楼层数为k，最坏的情况为尝试k次，因此至少需要k次才能确定鸡蛋从哪一层楼掉下去恰好摔碎。

有了最基本的情形还不够，对于其他的N，k并没有给出答案。这时，他想到自己这几天正在研究的算法：动态规划法，他想也许这个算法可以帮上忙。假设用numdrops(N,k)表示该问题的解。则将鸡蛋从x层扔下，有以下两种情形：

*  鸡蛋摔碎了，此时剩下N-1个鸡蛋，需要考虑比x层低的楼层，即1,2,…,x-1层，因为比x层高的楼层扔下去必定也摔碎，故可不比考虑。因此，这个问题会被缩减到numdrops(N-1, x-1).
 *  鸡蛋没有摔碎，此时剩下N个鸡蛋，需要考虑比x层高的楼层，即x+1, x+2,…,k层，共有k-x层。因此，问题会被缩减到numdrops(N, k-x).

对于以上两种情形，应该去两者的最大值。同时，考虑到x=1,2,3,…,k， 因此有如下公式：

numdrops(N,k)=1\+min1≤x≤k\{  max(numdrops(N−1,x−1),numdrops(N,k−x))\}.  n u m d r o p s ( N , k ) = 1 + min 1 ≤ x ≤ k \{   m a x ( n u m d r o p s ( N − 1 , x − 1 ) , n u m d r o p s ( N , k − x ) ) \} .

有了以上算法，再加上如下初始情况:

*  numdrops(0, x)=0, numdrops(x,0)=0.
 *  numdrops(1, x)=x.

就可以用动态规划法求解该问题了。他迅速地写下了Python代码：

import numpy as np
    
    def solvepuzzle(n, k):
        numdrops = np.array([[0]*(k+1)]*(n+1))
    
        for i in range(k+1):
            numdrops[1, i] = i
    
        for i in range(2, n+1):
            for j in range(1, k+1):
                minimum = float('inf')
    
                for x in range(1, j+1):
                    minimum = min(minimum, (1+max(numdrops[i, j-x], numdrops[i-1, x-1])))
    
                numdrops[i, j] = minimum
    
        print(numdrops)
        return numdrops[n,k]
    
    t = solvepuzzle(3, 10)
    print(t)

输出结果如下：

[[ 0 0 0 0 0 0 0 0 0 0 0] [ 0 1 2 3 4 5 6 7 8 9 10] [ 0 1 2 2 3 3 3 4 4 4 4] [ 0 1 2 2 3 3 3 3 4 4 4]]
    4

这样就可以求出该问题的解了，比如4个鸡蛋10层楼，则只需要3次即可。  
  丁丁连忙把这个解答问题通过助手告诉了科学家。科学家听后兴奋不已，立马叫丁丁过来讨论。科学家对他说道：“你的解决方法是如此的巧妙，让人叹为观止，很难相信它是出自一个少年的脑袋中。但是，亲爱的朋友，你能告诉我具体应该怎么扔鸡蛋呢？”  
  丁丁听了，又是欢喜又有点担心，因为科学家又提出了一个问题。他看看了输出的numdrops表格，立马就有了主意。  
  对于N=2，k=50的情形，numdrops(N,k)=10,给出的方案如下：

<table> 
 <thead> 
  <tr> 
   <th>从哪一层扔鸡蛋</th> 
   <th>鸡蛋摔碎后的情形</th> 
   <th>次数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>10</td> 
   <td>1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;6-&gt;7-&gt;8-&gt;9</td> 
   <td>9+1=10</td> 
  </tr> 
  <tr> 
   <td>19</td> 
   <td>11-&gt;12-&gt;13-&gt;14-&gt;15-&gt;16-&gt;17-&gt;18</td> 
   <td>8+2=10</td> 
  </tr> 
  <tr> 
   <td>27</td> 
   <td>20-&gt;21-&gt;22-&gt;23-&gt;24-&gt;25-&gt;26</td> 
   <td>7+3=10</td> 
  </tr> 
  <tr> 
   <td>34</td> 
   <td>28-&gt;29-&gt;30-&gt;31-&gt;32-&gt;33</td> 
   <td>6+4=10</td> 
  </tr> 
  <tr> 
   <td>40</td> 
   <td>35-&gt;36-&gt;37-&gt;38-&gt;39</td> 
   <td>5+5=10</td> 
  </tr> 
  <tr> 
   <td>45</td> 
   <td>41-&gt;42-&gt;43-&gt;44</td> 
   <td>4+6=10</td> 
  </tr> 
  <tr> 
   <td>49</td> 
   <td>46-&gt;47-&gt;48</td> 
   <td>3+7=10</td> 
  </tr> 
  <tr> 
   <td>50</td> 
   <td></td> 
   <td>8</td> 
  </tr> 
 </tbody> 
</table>

尝试着对上表做说明：先从第10层扔下，若鸡蛋摔了，则还剩一个鸡蛋，依次从1,2,3…9层扔下，若鸡蛋没碎，则失去了一次尝试机会，再将鸡蛋从19层扔下，若鸡蛋碎了，则还剩一个鸡蛋，依次从11,12,…,18层扔下……

对于N=4，k=20的情形，numdrops(N,k)=10,输出的numdrops表如下：

[[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
     [ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20]
     [ 0  1  2  2  3  3  3  4  4  4  4  5  5  5  5  5  6  6  6  6  6]
     [ 0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  5  5  5  5  5  5]
     [ 0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4  5  5  5  5  5]]
    5

首先找到numdrops(3,14)=4, 次数比5小一次， 层楼k尽可能大，则将鸡蛋从15扔下，若鸡蛋没碎，则剩下3个鸡蛋，探索4层楼，因为numdrops(3,14)=4，故能完成。若鸡蛋碎了，则再找到numdrops(2,6)=3,则将鸡蛋从7楼扔下，若鸡蛋碎了，则情形转化为numdrops(2,6)的情形，若鸡蛋没碎，则用剩下的鸡蛋探索7层楼，是可以搞定的。  
  当科学家看到这个结果后，满意地点点头，他想着是否要聘请这个少年来当自己的助手。不过，他决定再考验丁丁一回~~  
  未完待续~~

***注意：***本人现已开通两个微信公众号： 用Python做数学（微信号为：python\_math）以及轻松学会Python爬虫（微信号为：easy\_web\_scrape）， 欢迎大家关注哦~~