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