当前位置:   article > 正文

动态规划法(六)鸡蛋掉落问题(一)_深圳大学动态规划法扔鸡蛋

深圳大学动态规划法扔鸡蛋

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

动态规划法解决egg dropping problem~

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

 

 

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

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

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

  1. import numpy as np
  2. def solvepuzzle(n, k):
  3. numdrops = np.array([[0]*(k+1)]*(n+1))
  4. for i in range(k+1):
  5. numdrops[1, i] = i
  6. for i in range(2, n+1):
  7. for j in range(1, k+1):
  8. minimum = float('inf')
  9. for x in range(1, j+1):
  10. minimum = min(minimum, (1+max(numdrops[i, j-x], numdrops[i-1, x-1])))
  11. numdrops[i, j] = minimum
  12. print(numdrops)
  13. return numdrops[n,k]
  14. t = solvepuzzle(3, 10)
  15. print(t)

输出结果如下:

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

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

从哪一层扔鸡蛋鸡蛋摔碎后的情形次数
101->2->3->4->5->6->7->8->99+1=10
1911->12->13->14->15->16->17->188+2=10
2720->21->22->23->24->25->267+3=10
3428->29->30->31->32->336+4=10
4035->36->37->38->395+5=10
4541->42->43->444+6=10
4946->47->483+7=10
50 8

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

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

  1. [[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
  2. [ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
  3. [ 0 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6]
  4. [ 0 1 2 2 3 3 3 3 4 4 4 4 4 4 4 5 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]]
  6. 5

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/723580
推荐阅读
相关标签
  

闽ICP备14008679号