Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Problem number 18 from Project Euler's site is as follows:

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

The formulation of this problems does not make clear if

  • the "Traversor" is greedy, meaning that he always choosed the child with be higher value
  • the maximum of every single walkthrough is asked

The NOTE says, that it is possible to solve this problem by trying every route. This means to me, that is is also possible without!

This leads to my actual question: Assumed that not the greedy one is the max, is there any algorithm that finds the max walkthrough value without trying every route and that doesn't act like the greedy algorithm?

I implemented an algorithm in Java, putting the values first in a node structure, then applying the greedy algorithm. The result, however, is cosidered as wrong by Project Euler.

sum = 0;

void findWay(Node node){
    sum += node.value;
    if(node.nodeLeft != null && node.nodeRight != null){
            if(node.nodeLeft.value > node.nodeRight.value){
                findWay(node.nodeLeft);
            }else{
                findWay(node.nodeRight);
            }
        }
}
share|improve this question
1  
Sometimes choosing the lower number will result in choosing a higher number on the next choice, one high enough to offset the differencec in the previous choice, this is why your algorithm is wrong. –  Jimmy Hoffa Nov 30 '12 at 23:49
    
Of course it is, but is this asked in the problem? –  Valentino Ru Nov 30 '12 at 23:50
    
"maximum total" to me means exactly that. Maximum is an absolute word, so read it as "absolute maximum total possible". –  Jimmy Hoffa Nov 30 '12 at 23:56
2  
I'd tackle it with a modified Dijkstra's algorithm I think. I'll try it out tomorrow. It should let you figure quickly when to early-terminate a route. Maybe there's a better way... there goes my good night's sleep. –  James Dec 1 '12 at 1:50
    
This is typically an example of a dynamic programming problem, which can often appear to be solvable with a greedy method. Dynamic programming requires the solution of subproblems to solve the main problem. –  Peter Smith Dec 1 '12 at 1:59

4 Answers 4

up vote 7 down vote accepted

Spoiler alert: This answer leads you to a solution, but does not implement it


Using WuHoUnited's example, modified for uniqueness:

   9
  7 0
 2 4 6
8 5 1 3

Ask yourself this: If you found yourself at 2, would you ever take 8 instead of 5, knowing they are the leaf nodes of the tree? Similarly, If you found yourself at 6, would you ever take 3 instead of 1, knowing those are the leaf nodes of the tree?

Certainly not. We can now reduce the tree, knowing what decision we'd take at the penultimate branch (regardless of how we got there):

   9
  7 0
10 9 9

I think you see where this is going.

share|improve this answer

As somebody who has solved the problem I can tell you that the greedy algorithm is NOT what they are looking.

It is looking for the maximum value of all possible routes.

example

   3
  7 4
 2 4 6
8 5 1 3

3+7+4+5 = 19 <- greedy
3+7+2+8 = 20 <- not greedy

So the answer should be 20

share|improve this answer
    
ok but this will mean that there is no other way than walk every route, isn't it? –  Valentino Ru Dec 1 '12 at 0:54
1  
@ValentinoRu obviously not, the euler problem says so. This is a graph problem, so try drawing graphs with the small number sets in various ways and see if you can identify any representations of them that brings the information you want to the forefront. –  Jimmy Hoffa Dec 1 '12 at 1:05
    
It is like Project Euler and Jimmy Hoffa say: There is a very efficient way to solve the problem without trying every route. –  WuHoUnited Dec 1 '12 at 1:17

Dijkstra's algorithm for shortest paths (turn all edges negative).

share|improve this answer
5  
You could be a little more verbose in your answer. Even a link to Dijkstra's algorithm would be more helpful. –  Martijn Pieters Dec 1 '12 at 13:21

Greedy approach is definitely not the approach you should consider for this problem. Think of a solution that exhaustively checks all possible routes and find the maximum. Then optimize it using Dynamic programming.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.