Author |
Topic: Pyramid Problem (Read 2110 times) |
|
witee
Newbie
Posts: 48
|
 |
Pyramid Problem
« on: Jul 20th, 2010, 9:32pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Jul 20th, 2010, 9:32pm by witee » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Pyramid Problem
« Reply #1 on: Jul 21st, 2010, 12:09am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
common
Newbie
Posts: 1
|
|
Re: Pyramid Problem
« Reply #2 on: Jul 21st, 2010, 2:55am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Pyramid Problem
« Reply #3 on: Jul 21st, 2010, 5:32am » |
Quote Modify
|
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;
}
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Pyramid Problem
« Reply #4 on: Jul 24th, 2010, 7:24am » |
Quote Modify
|
on Jul 20th, 2010, 9:32pm, witee wrote: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. |
|
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 ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print