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

2021-10-04 11:42:59

继续讲故事~~
这天，丁丁正走在路上，欣赏着路边迷人的城市风景，突然发现前面的大楼前围了一波吃瓜群众。他好奇地凑上前去，想一探究竟，看看到底发生了什么事情。
原来本市的一位小有名气的科学家正在这幢大楼进行一个实验：某种材料的防护性能。他在大楼的底下铺了一层这种防护材料，想拿鸡蛋做实验，将鸡蛋从楼层掉下，看看鸡蛋从哪一层掉下去会摔碎，以此测试该材料的防护性能。这就是著名的鸡蛋掉落问题（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，因此有如下公式：

n u m d r o p s (N, k) = 1 + min 1 \leq x \leq 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,给出的方案如下：

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

尝试着对上表做说明：先从第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），欢迎大家关注哦~~

码农公寓

相关文章