wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Pyramid Problem
        
(Message started by: witee on Jul 20^th, 2010, 9:32pm)

Title: Pyramid Problem
Post by witee on Jul 20^th, 2010, 9:32pm

Given an array of integers.....
Imagine it as a pyramid as below:

a[]={1,2,3,4,5,6,7,8,9,10}
1
2 3
4 5 6
7 8 9 10
find a path from level 1 to last level such that the sum is maximum.... The path is such that its children should be reachable.
Ex:
1,2,5,9 is a path
1,2,6,10 is not a path since 6 is not reachable from 2.
The array is not sorted and numbers are random.

Title: Re: Pyramid Problem
Post by towr on Jul 21^st, 2010, 12:09am

Sounds like a dynamic programming problem. For each level in the pyramid find for each element the maximum path leading there, then construct the next level based on the previous.

Title: Re: Pyramid Problem
Post by common on Jul 21^st, 2010, 2:55am

We can achieve the solution for this problem by using the back tracking method.
step-1:
1
2 3
4 5 6
7 8 9 10
step-2:
1
2 3
12 14 16
7 8 9 10
step-3:
1
16 19
12 14 16
7 8 9 10
step-4:
20
16 19
12 14 16
7 8 9 10

From this step we can see the maximum possible value is 20 and the corresponding path is: 1->3->6->10.

Title: Re: Pyramid Problem
Post by Grimbal on Jul 21^st, 2010, 5:32am

I wouldn't call that backtracking but just computing the max path value from the bottom up.

Here is a java implementation.

public static int[] maxPath(int[] a)
{
int size = (int)Math.sqrt(2*a.length);
if( a.length != size*(size+1)/2 ){
throw new InvalidParameterException("Invalid input size.");
}
int[] b = new int[a.length];
int n = a.length;
for( int i=0 ; i<size ; i++ ){
n--;
b[n] = a[n];
}
for( int rowSize = size-1 ; rowSize>0 ; rowSize-- ){
for( int i=0 ; i<rowSize ; i++ ){
n--;
b[n] = a[n] + Math.max( b[n+rowSize], [n+rowSize+1] );
}
}
int[] path = new int[size];
int p = 0;
n = 0;
path[p++] = a[0];
for( int rowSize=1 ; rowSize<size ; rowSize++ ){
n += rowSize;
if( b[n+1]>b[n] ) n++;
path[p++] = a[n];
}
return path;
}

Title: Re: Pyramid Problem
Post by birbal on Jul 24^th, 2010, 7:24am

on 07/20/10 at 21:32:15, witee wrote:

When you say "children", does it mean lower and lower right number, or is it include lower left as well ( if exists )
for example, is 4 a child of 3 ?