Egg Dropping Algorithm
The Egg Dropping Algorithm is a popular optimization problem in computer science and mathematics, which deals with finding the minimum number of trials required to determine the highest floor in a building from which an egg can be dropped without breaking. The problem assumes that there are a certain number of floors in the building and that an egg will break if dropped from a floor above a certain threshold, while remaining intact if dropped from a floor below that threshold. The objective is to minimize the number of trials needed to identify this threshold floor, given a limited number of eggs to conduct experiments.
The algorithm employs a dynamic programming approach to solve this problem, where the optimal solution is constructed by combining the results of subproblems. The algorithm considers various scenarios and computes the minimum number of trials required for each combination of floors and eggs. It uses a two-dimensional table to store the results of these subproblems, where each cell represents the minimum number of trials needed for a given number of floors and eggs. The algorithm iteratively updates the table by considering the worst-case scenarios for each trial, and finally, the cell containing the minimum number of trials for the given problem is returned as the solution. This approach not only minimizes the number of trials but also reduces the time complexity, making it an efficient solution for the egg dropping problem.
package DynamicProgramming;
/**
* DynamicProgramming solution for the Egg Dropping Puzzle
*/
public class EggDropping {
// min trials with n eggs and m floors
private static int minTrials(int n, int m) {
int[][] eggFloor = new int[n + 1][m + 1];
int result, x;
for (int i = 1; i <= n; i++) {
eggFloor[i][0] = 0; // Zero trial for zero floor.
eggFloor[i][1] = 1; // One trial for one floor
}
// j trials for only 1 egg
for (int j = 1; j <= m; j++)
eggFloor[1][j] = j;
// Using bottom-up approach in DP
for (int i = 2; i <= n; i++) {
for (int j = 2; j <= m; j++) {
eggFloor[i][j] = Integer.MAX_VALUE;
for (x = 1; x <= j; x++) {
result = 1 + Math.max(eggFloor[i - 1][x - 1], eggFloor[i][j - x]);
// choose min of all values for particular x
if (result < eggFloor[i][j])
eggFloor[i][j] = result;
}
}
}
return eggFloor[n][m];
}
public static void main(String args[]) {
int n = 2, m = 4;
// result outputs min no. of trials in worst case for n eggs and m floors
int result = minTrials(n, m);
System.out.println(result);
}
}
