广义双蛋拼图

Question

这是问题描述:

假设我们想知道N层建筑中的哪些故事可以安全地从中掉落鸡蛋,哪些会导致鸡蛋在着陆时破裂.我们做了一些假设:可以再次使用在摔倒后存活的鸡蛋.

• 必须丢弃破蛋.
• 所有鸡蛋的跌倒效果都是一样的.
• 如果鸡蛋在掉落时断裂,那么如果从较高的窗口掉落则会破裂.
• 如果一个鸡蛋在摔倒后存活,那么它会在较短的摔倒后存活.
• 不排除一楼的窗户打破鸡蛋,也不排除N楼的窗户不会导致鸡蛋破裂.

给定一个N层建筑和一个鸡蛋供应,找到最小化(在最坏的情况下)确定断裂所需的实验滴数的策略.

---

我已经看到并解决了2个鸡蛋的问题,其中答案是14 = N = 100.我尝试使用DP了解wiki的通用解决方案,但无法理解他们想要做什么.请告诉他们他们是如何到达DP以及它是如何工作的？

编辑:

本条中给出的最高流量可用d滴和e蛋测试的复发如下:

f[d,e] = f[d-1,e] + f[d-1,e-1] + 1

复发很好,但我无法理解它是如何衍生出来的？

这个解释对我来说并不清楚....我只是希望有人用更清晰的话语向我解释这种情况.

Answer 1

(1)考虑第一滴打破鸡蛋的情况.然后,当且仅当它最多为f [d-1,e-1]时,您才能确定断裂地板.因此,你不能高于f [d-1,e-1] + 1(当然不应该低于f).

(2)如果你的第一滴没有打破鸡蛋,你就是f [d-1,e]的情况,只是从你的第一滴+ 1的地板开始,而不是从1楼开始.

所以,你能做的最好就是开始在地板f [d-1,e-1] + 1(因为(1))下降鸡蛋,你可以达到f [d-1,e]楼层比那(因为(2)).那是

f[d, e] = f[d-1, e-1] + 1 + f[d-1, e]

Answer 2

从Wiki Egg Dropping puzzle我们知道状态转移方程是:

W(n,k) = 1 + min{ max(W(n ? 1, x ? 1), W(n,k ? x)) } , x = 1, 2, ..., k

W(n,1)=1, W(1,k)=k

n =可用的试验蛋数量

k =尚待测试的(连续)楼层数

以下是我的理解.

我们有k地板,n鸡蛋,假设我们用鸡蛋在x地板上测试.只有两种可能的结果:

1. 它打破了,所以问题递归地来到:x-1地板,n-1鸡蛋,反映到W(n-1,x-1)
2. 它没有破坏,所以问题递归地来到:k-x地板,n鸡蛋,它反映到W(n,k-x)

由于问题需要最坏的情况,我们必须选择较大的一个以确保最坏的情况有效,这就是我们在W(n-1,x-1)和之间添加最大值的原因W(n,k-x).

此外,正如我们刚刚假设在x地板x上进行测试,可以从中1到k,在这种情况下,我们肯定需要选择最小值以确保最小实验滴数找出N,这就是为什么我们在 {max(W(n ? 1, x ? 1), W(n,k ? x)): x = 1, 2, ..., k}

最后,因为我们使用1了x floor的下降,所以方程式必须加上1,这反映了方程的第一部分.

希望能解决你的难题:-)