package DP;
/**
* 100层楼,两个鸡蛋。某层之上扔鸡蛋就会碎。问至少要测试多少次才能找出这层楼来
* 我们可以决定怎么扔(min),但必须假设我们的运气最差(max)
*
* 100层楼,两个鸡蛋。某层之上扔鸡蛋就会碎。问至少要测试多少次才能找出这层楼来?
思路:
首先要理解清楚题意,本题不是要找在哪一层以上会把鸡蛋扔破!而是我们假设在W层以上会把鸡蛋仍破,现在问至少要测试Y次才能找到这个W层?求的是Y
另外一个要注意的是本题中要基于扔的人运气最差的情况,即要保证在worst case下也能找到。
定义W层位蛋破层,则
我们第一次从第x层扔蛋下去,有两种可能:
1) 蛋破了:这说明了两点 1.我们手上仍然有n-1颗蛋 2.蛋破层一定在1...x-1之间,这里共有x-1-1+1 =>x-1数量的嫌疑楼层
2)蛋没破:这也说明了两点 1.我们手上仍然有n颗蛋 2.蛋破层一定在x+1...k之间,这里共有k-(x+1)+1 =>k-x数量的嫌疑楼层
定义eggDrop(n, k)为在最差情况下找出蛋破层所需要的最少扔数。n为蛋的数量,k为要检查的连续的楼层的数量
因为我们要基于最差情况,所以我们要选择两种可能之间更坏的那种,即导致扔的数量更多的那种情况,
即max(eggDrop(n - 1, x - 1), eggDrop(n, k - x))
然后我们遍历所有楼层,要找出能使得最后扔的数量最小的那个初始楼层,因此
eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): x in {1, 2, ..., k}}
加1是因为在第x层测试时也消耗了1次。
*/
public class EggDroppingPuzzle {
public static void main(String[] args) {
int n = 2, k = 20;
System.out.println(eggDropDP(n, k));
System.out.println(eggDropRec(n, k));
}
/* Function to get minimum number of trails needed in worst
case with n eggs and k floors */
// n: 手上完好蛋的数量
// k: 要测试的连续楼层的数量
public static int eggDropRec(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;
/**
我们要决策怎么扔使得总扔数最少(即使在我们运气最差的情况下)worst-case
所以在每一楼都测试第一扔,然后递归计算出总共需要的扔数,找到扔数最小的数量
所以假设在第x层扔第一个蛋:
结果1:蛋破了->现在我们只有n-1个蛋,还要测试x-1数量的楼层[1,x-1] -> 数量=x-1 -1 + 1 = x-1
结果2: 但没破 -> 现在我们仍有n个蛋,还要测试k-x数量的楼层[x+1,k] -> 数量=k - (x+1) + 1 = k-x
*/
for(int x=1; x<=k; x++){
int res = Math.max(eggDropRec(n-1, x-1), eggDropRec(n, k-x));
min = Math.min(min, res);
}
return min+1; // +1是因为测试当前层消耗了一次扔
}
/* Function to get minimum number of trails needed in worst
case with n eggs and k floors */
// Time Complexity: O(nk^2), Auxiliary Space: O(nk)
public static int eggDropDP(int n, int k){
/* A 2D table where entery dp[i][j] will represent minimum
number of trials needed for i eggs and j floors. */
int[][] dp = new int[n+1][k+1];
// We need one trial for one floor and0 trials for 0 floors
for(int i=1; i<=n; i++){
dp[i][1] = 1;
dp[i][0] = 0;
}
// We always need j trials for one egg and j floors.
for(int j=1; j<=k; j++){
dp[1][j] = j;
}
// Fill rest of the entries in table using optimal substructure
// property
for(int i=2; i<=n; i++){ // i eggs
for(int j=2; j<=k; j++){ // j floors
dp[i][j] = Integer.MAX_VALUE;
for(int x=1; x<=j; x++){ // try every floor from 1...j
int res = 1 + Math.max(dp[i-1][x-1], dp[i][j-x]);
dp[i][j] = Math.min(dp[i][j], res);
}
}
}
return dp[n][k];
}
}
分享到:
相关推荐
C#,动态规划(DP)丢鸡蛋问题(Egg Dropping Puzzle)的三种算法与源代码 动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等...
Dropping-Thunder:Dropping Thunders TD模拟器
JavaScript
textlint-rule-no-dropping-i这是一个检测丢失单词的规则。 are我们正在发展。 developing我在发展。安装npm install @textlint-ja/textlint-rule-no-dropping-i用法将@textlint-ja/textlint-rule-no-dropping-i ....
语言:English通过空中景观放下苹果,绝对不会错过重要的掉苹果活动,例如小睡放苹果可以帮助您与商店的预购开店保持最新并保持个人时间表...使用Airscape的Dropping Apple绝不会错过重要的Apple Droping事件,例如小睡
BallDropping是一个会让人上瘾的噪音制造器,如果平时无聊的时候也可以当作小游戏来玩。很多小球从天而降,根据碰击角度、速度的不同,掉在鼠标划的线上会发出大珠小珠落玉盘的声音。 <br>你可不要小看了...
人が来れないんです安装npm install textlint-rule-no-dropping-the-ra用法将“ no-drop-the-ra” .textlintrc { " rules " : { " no-dropping-the-ra " : true }}贡献叉吧! 创建功能分支: git checkout -b my-new...
gps测试,jieshougps数据存储数据库,检测发送命令地
Call dropping performance analysis of the eNB-first channel access policy in LTE-Advanced relay networks
偏好(或批准)投票表以选择选举竞赛的优胜者或排名决定。 使用丢弃成本最小化来组合两种Condorcet方法:克隆Schwartz顺序丢弃和Tideman的排名对。
This paper is concerned with the distributed fusion estimation in sensor networks where local estimates are sent to a fusion centre for fusion estimation, with random delays and packet dropouts....
TCL script to find wireless packet dropping nodes2609002STC12C5A60S2+2.4TFT+DS1302+DS18B20+GPS+FM 自动校时收音机电子钟 STC12C5A60S2+2.4TFT+DS1302+DS18B20+GPS+FM 自动校时收音机电子钟 捣鼓了许久
中文版文档 Emoji Rain Hey, it's raining emoji! This is a really simple and funny animation for Android. You could find similar ...How many emojis will dropping in each flow, default 6 duration
当VirtualBox 2.1.4升级到2.2.0以后,突然发现虚拟的系统无法使用主机的网络上网了,google了一下,发现很多人碰到这个问题,但没有解决办法,甚至有人认为是VirtualBox的Bug,其实不然。 经过研究发现,2.2.0缺省...
2D滴入式软体 自学项目我一直对计算机模拟物理世界充满热情。 最近,我试图在二维中模拟与刚体碰撞时的软体变形。 该程序仍未完成,但是现在我将其留在这里,过一会儿我将返回它。
Qt Serialbus 报错 dropping older ADU fragments due to larger than 3.5 char 用qt打开此项目编译安装即可解决
35个用户在1000time slot中,以0.2的概率产生packets
抛球游戏 827游戏的第一款游戏
dropping probabilities, i.e., the packet dropping probability due to energy depletion and that due to channel error. Numerical examples are provided to illustrate the theoretical findings, and new ...
Chapter 7: Creating and Dropping 183 Chapter 8: Creating Users and Granting Access 219 Chapter 9: Date and Time Values 247 Chapter 10: Aggregate Functions and Clauses 279 Chapter 11: SELECT ...