#
Optimum Grid Harvest

/********************************************************************* * Author: Isai Damier * Title: Optimum Grid Harvest * Project: geekviewpoint * Package: algorithms * * Statement: * Given n boxes of avocados tightly arranged in a h*w grid, and given * that you may only move down or to the right, amass the maximum * number of avocados. * * Time-complexity: O(n) * * Dynamic Programming Strategy: * * As it turns out this problem is easily solved by considering one * box of avocado at a time. For each box of avocado: look up, look left, * then pick the box that has more avocados and add it to the box on * which you are standing. * * Here is how you might go about it: * 0] Think of the boxes of avocados as an A[1..h][1..w] matrix or array. * 1] Take a sheet of paper and draw an h*w grid on it. Say V[1..h][1..w]. * 2] In the upper-left cell, V[0][0], write the number of avocados * that's in the corresponding box: so V[0][0] = A[0][0]. This is * because at A[0][0] there is nothing to the left or above. Simple. * 3] Imagine you took your next step to the right, then after looking * up and looking left, you would have all the avocados in A[0][0] * plus those in A[0][1]. Hence, cell V[0][1] would have * V[0][0]+A[0][1] avocados. Again there is if you look up. * 4] But if instead of going right you went down, then after looking * up and looking left, you would have all the avocados in A[0][0] * plus those in A[1][0]. So that cell V[1][0] would have * V[0][0]+A[0][1] avocados. (there is if you look left.) * 5] After filling each new cell on your sheet of paper, you can fill * the next cell by evaluating the same possibilities as in step 3 * and step 4. So your overall process is * * V[i][j]=A[i][j] + max(V[i-1][j],V[i][j-1]) * * 6] When you are done with cell V[h][w], it will have the maximum * number of avocados you can amass. * * Of course in a real implementation, unless you are told not to modify * the input array A[1..h][1..w] you can double it as V[1..h][1..w]. In * this implementation, we assume we should not touch the original. * * DETAILS YOU MAY NOT CARE FOR: * * You could summarize the strategy above as follows: * * For each box we consider, we actually calculate the optimum solution * up to that box. Further, to calculate the next box, we use the * solutions for the previous boxes. So really we start with a small * grid and then keep solving for larger and larger grids until we * reach the final answer. Hence, we say the problem shows Optimal * Substructures: each smaller segment of the grid is a grid, and the * optimal solution to a smaller grid can be applied for solving a * larger grid. * * Additionally, the grids overlap. What we mean is the grid * A[1..i][1..j] is contained in A[1..i][1..j+1] which in turn is * contained in A[1..i+1][1..j+1] up until A[1..h][1..w]. Hence, * some of the smaller grids are actually completely parts of the * larger grids. This trait is referred to as Overlapping Subproblems. * * Consequently, although we already knew that our strategy is * Dynamic Programming, we can confirm that indeed it is Dynamic * Programming since we used a table (i.e. V[1..h][1..w]) to solve * a problem that exhibits both optimal substructures and overlapping * subproblems. You may also hear the word memoize, which basically * means we use V[1..h][1..w] to write down memos about each subproblem * we solve. **********************************************************************/ public int gridHarvest(int[][] grid) { if (null == grid) { return 0; } int[][] value = new int[grid.length][grid[0].length]; int xMax = grid.length - 1; int yMax = grid[0].length - 1; for (int x = 0; x <= xMax; x++) { for (int y = 0; y <= yMax; y++) { amass(grid, x, y, value); } } return value[xMax][yMax]; } private void amass(int[][] grid, int x, int y, int[][] value) { if (0 < x && 0 < y) { value[x][y] = grid[x][y] + Math.max(value[x - 1][y], value[x][y - 1]); } else if (0 < x) { value[x][y] = grid[x][y] + value[x - 1][y]; } else if (0 < y) { value[x][y] = grid[x][y] + value[x][y - 1]; } else { value[x][y] = grid[x][y]; } }

package algorithm.programming.dynamic; import java.util.Arrays; import java.util.List; import org.junit.Test; import static org.junit.Assert.*; public class HarvestingTest { /** * Test of gridHarvest method, of class Harvesting. */ @Test public void testGridHarvest() { System.out.println("gridHarvest"); int[][] grid = { {51, 42, 33, 25, 18}, {13, 21, 34, 55, 89}, {82, 63, 45, 27, 11}, {13, 17, 19, 23, 29} }; Harvesting instance = new Harvesting(); int expResult = 344; int result = instance.gridHarvest(grid); assertEquals(expResult, result); } /** * Test of gridHarvest method, of class Harvesting. */ @Test public void testGridHarvest7() { System.out.println("gridHarvest"); int[][] grid = { {51, 92, 93, 97, 98}, {13, 21, 34, 55, 89}, {82, 63, 45, 27, 11}, {13, 17, 19, 23, 29} }; Harvesting instance = new Harvesting(); int expResult = 560; int result = instance.gridHarvest(grid); assertEquals(expResult, result); } /** * Test of gridHarvest method, of class Harvesting. */ @Test public void testGridHarvestL() { System.out.println("gridHarvest"); int[][] grid = { {51, 42, 33, 25, 18}, {93, 21, 34, 55, 89}, {92, 63, 45, 17, 11}, {93, 67, 59, 23, 29} }; Harvesting instance = new Harvesting(); int expResult = 507; int result = instance.gridHarvest(grid); assertEquals(expResult, result); } }