Re: Urgent Recurrence Problem, Please Help !

On Oct 29, 3:21 pm, gw7...@xxxxxxx wrote:
On 29 Oct, 08:06, Tonny <tonnysp...@xxxxxxxxx> wrote:

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!!!

OK. Let B(i) be the best score you can get if you satisfy the given
conditions and you are also not allowed to use any of the numbers
before i. So B(1) is the problem you are trying to solve.

Now, if you want to work out B(1), you have to decide whether to
include V(1) or not. If you don't include it, you can include any of
the later numbers (subject to the original conditions) and so B(1) =
B(2). Alternatively, if you do include V(1), you get the points for
that but you can't include any more numbers before number W(1)+2. But
you can include any after that. So in this case B(1) = V(1) +
B(W(1)+2). So the actual B(1) will be the greater of these two
possibilities.

In the same way, each B(i) can be written as the greater of two
possibilities. I'll let you do that bit, including dealing with the
case where W(i) is so large that you don't get to choose any further
numbers.

Now that you have a recursive formula, you can calculate the actual
values. Start at B(N) (which is of course W(N)) and work backwards.

Hope this helps.
Paul.

Hi Paul,

Thank you so much. Your suggestion helps a lot!!!

Best regards,
Tonny

.

Relevant Pages

  • Re: Urgent Recurrence Problem, Please Help !
    ... the later numbers (subject to the original conditions) and so B= ... Now that you have a recursive formula, ... Start at B) and work backwards. ...
    (comp.programming)
  • Re: hex zero revisited
    ... Jolly Roger wrote: ... A zero is a zero, ... However numbers work backwards on some processors.. ... Take this posting and apply it as machine code to a Z80..it will TRY and make something of it..;) ...
    (comp.sys.mac.system)