Re: Urgent Recurrence Problem, Please Help !

On Oct 29, 9:11 am, heiner.mar...@xxxxxxxx (Heiner Marxen) wrote:
In article <1193644969.455245.247...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Tonny <tonnysp...@xxxxxxxxx> writes:

There are two integer lists: V(1..N) and W(1..N)
V(i) is positive and W(i) is non-negative for all i. (i.e. W(i) can be
zero)

Now I'm going to select the elements from the V list, the constraint
is : if I pick V(i), then I must avoid taking V(i+1),V(i+2),..., V( i+
W (i) )

The problem is how to maximize the sum of the V's I can select.

Can anyone help me out by using a recursive way? Thanks a lot!!!

Did you notice, that you can solve this linearly, i.e. without
any recursion?

Just tabulate the optimal solutions for the suffixes
V(k..N) and W(k..N) for k=n downto 1,
by doing a single case analysis (take or not take V(k)),
using the already computed (and tabulated) data of the
shorter suffixes.

HTH,
--
Heiner Marxen http://www.drb.insel.de/~heiner/

Hi Heiner,

Thanks for replying. Actually it's only one part of my work and I am
looking for a way of dynamic programming, so...that's why i need to
express it in a recursive way.

Thanks.

Tonny

.