Popular Posts

Monday, April 11, 2011

Apple Problem

A table composed of N*M cells,each having a certain quantity of apples, is given. you start from the upper-left corner. At each step you can go down or right one cell.Design an algorithm to find the maximum number of apples you can collect ,if you are moving from upper-left corner to bottom-right corner. 
Here is a code for solving the problem using Dynamic programming :

Java code :
public class AppleProblem {
public static void main(String[] args) {
int[][] apples = { { 2, 3, 1 }, { 4, 6, 2 }, { 7, 8, 2 } };

int rows = apples.length;
int columns = apples[0].length;

// Create a temporary array to store the maximum sum upto that position
int[][] dp = new int[rows][columns];

int prevRowValue = 0;
int prevColumnValue = 0;

for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {

if (i - 1 < 0)
prevRowValue = 0;
else
prevRowValue = dp[i - 1][j];

if (j - 1 < 0)
prevColumnValue = 0;
else
prevColumnValue = dp[i][j - 1];

dp[i][j] = apples[i][j] + max(prevRowValue, prevColumnValue);
}
}
System.out.println(dp[rows - 1][columns - 1]);
}

private static int max(int a, int b) {
return a > b ? a : b;
}
}

No comments:

Post a Comment