Need help with dynamic programming problem

Posted by John Retallack on Stack Overflow See other posts from Stack Overflow or by John Retallack
Published on 2010-04-08T22:30:25Z Indexed on 2010/04/08 22:33 UTC
Read the original article Hit count: 497

Filed under:

I have the following problem : I am given a tree with N apples, for each apple I am given it's weight and height,I can pick apples up to a given height H,each time I pick an apple the height of every apple is increased with U(also given).I have to find out the maximum weight of apples I can pick.

e.g:
N=4 H=100 U=10
(height-eight)
apple1: 91 10
apple2: 82 30
apple3: 93 5
apple4: 94 15

The answer is 45 : I first pick the apple with the weight of 15 then the one with the weight of 30.

I would like to know if someone here could help me with giving me an hint on how I should approach this problem.

Thank you.

Related posts about dynamic-programming

Dynamic Programming Recursion and a sprinkle of Memoization

as seen on Stack Overflow - Search for 'Stack Overflow'
I have this massive array of ints from 0-4 in this triangle. I am trying to learn dynamic programming with Ruby and would like some assistance in calculating the number of paths in the triangle that meet three criterion: You must start at one of the zero points in the row with 70 elements. Your… >>> More
dynamic programming [closed]

as seen on Stack Overflow - Search for 'Stack Overflow'
the input to this problem is a sequence S of integers(not necessarily positive). the problem is to find consecutive subsequence of S with maximum sum using dynamic programming. consecutive means that you are not allowed to skip numbers. for example: if the input was 12,-14,1,23,-6,22,-34,-13. the… >>> More
Need help with dynamic programming problem

as seen on Stack Overflow - Search for 'Stack Overflow'
I have the following problem : I am given a tree with N apples, for each apple I am given it's weight and height,I can pick apples up to a given height H,each time I pick an apple the height of every apple is increased with U(also given).I have to find out the maximum weight of apples I can pick.… >>> More
Algorithm and data structure learning resources for dynamic programming

as seen on Stack Overflow - Search for 'Stack Overflow'
Im learning dynamic programming now, and while I know the theory well, designing DP algorithms for new problems is still difficult. This is what i would really like now- A book or a website, which poses a problem which can be solved by dynamic programming. Also there is the solution with an explanation… >>> More
How to speed up calculation of length of longest common substring?

as seen on Stack Overflow - Search for 'Stack Overflow'
I have two very large strings and I am trying to find out their Longest Common Substring. One way is using suffix trees (supposed to have a very good complexity, though a complex implementation), and the another is the dynamic programming method (both are mentioned on the Wikipedia page linked above)… >>> More

Developer IT