# Recurrence equation calculation

I have a recurrece equation

Changed notations: $\qquad\displaystyle G(W) = \max \{ G(W - s_i) + v_i \mid 0 \leq i \leq n, w_i \leq W \}$,

I am not sure if I understand $\ w_i$ correctly.

On each iteration my $w_i \leq W$ . So my $w_i$ will be previous $W-s_i$ since G takes one argument?

• All you've given us is a formula. It doesn't consist of a recurrence relation. Also, it's not clear what $G,W,s_i,v_i,w_i$ are, and in particular, it's not clear why $w_i \leq W$ is relevant, since it doesn't appear on the expression being maximized. Have you copied everything correctly? Apr 14, 2018 at 14:06
• @YuvalFilmus you are right I forgot to add the original equation. The equation I inserted earlier was simplified because I did not understand the notations Apr 14, 2018 at 14:14
• It seems that the $w_i$ are additional parameters. There is apparently a typo in the definition: instead of $w_i \le w$, it should be $w_i \le W$. Apr 14, 2018 at 14:18
• The $w_i$, like the $s_i$ and $v_i$, are fixed and do not change during the recurrence. Apr 14, 2018 at 14:19
• Sorry if this question will sound dumb, so $w_i$ is not relevant if I am counting G(W) on i iteration? Or $w_i$ is $W-s_i$ on i iteration? @YuvalFilmus Apr 14, 2018 at 14:25

Here is pseudocode for computing your function:

Parameters:

• Integer $n$
• Arrays $W,V,S$ of length $n$

function G(w):

• If $w = 0$, return $0$
• Let $\mathrm{max} \gets -\infty$
• For $i$ from $1$ to $n$:
• If $W[i] \leq w$:
• Let $x \gets G(w-S[i])+V[i]$
• If $x > \mathrm{max}$, let $\mathrm{max} \gets x$
• Return $\mathrm{max}$

I used the notation $W[i],V[i],S[i]$ rather than $w_i,v_i,s_i$.