#
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. #======================================================================= def gridHarvest( grid ): if grid is None: return 0 value = [[0 for y in range( len( grid[0] ) )] for x in range( len( grid ) )] xMax = len( grid ) - 1 yMax = len( grid[0] ) - 1 for x in range( xMax + 1 ): for y in range( yMax + 1 ): amass( grid, x, y, value ) return value[xMax][yMax] def amass( grid, x, y, value ): if 0 < x and 0 < y: value[x][y] = grid[x][y] + max( value[x - 1][y], value[x][y - 1] ) elif 0 < x: value[x][y] = grid[x][y] + value[x - 1][y] elif 0 < y : value[x][y] = grid[x][y] + value[x][y - 1] else: value[x][y] = grid[x][y]

import unittest from dynamic_programming import Harvesting as harvest class Test( unittest.TestCase ): def testGridHarvest( self ): grid = [ [51, 42, 33, 25, 18], [13, 21, 34, 55, 89], [82, 63, 45, 27, 11], [13, 17, 19, 23, 29] ] expResult = 344 result = harvest.gridHarvest( grid ) self.assertEquals( expResult, result ) def testGridHarvest7( self ): grid = [ [51, 92, 93, 97, 98], [13, 21, 34, 55, 89], [82, 63, 45, 27, 11], [13, 17, 19, 23, 29] ] expResult = 560 result = harvest.gridHarvest( grid ) self.assertEquals( expResult, result ) def testGridHarvestL( self ): grid = [ [51, 42, 33, 25, 18], [93, 21, 34, 55, 89], [92, 63, 45, 17, 11], [93, 67, 59, 23, 29] ] expResult = 507 result = harvest.gridHarvest( grid ) self.assertEquals( expResult, result )