GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Algorithms-Java/Dynamic Programming/EggDropping.java at master · shexiao/Algorithms-Java Expand file tree/ Copy pathEggDropping.javaMore file actions 47 lines (36 loc) · 1.31 KB / Copy pathEggDropping.javaFile metadata and controls47 lines (36 loc) · 1.31 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 /** * Dynamic Programming 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); } } |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |