# Syntax of recurrence formula not clear

I have this task for Analysis of Algorithms module in university

\begin{align*} W, V &= \{v_1, v_2, v_n\}, S = \{s_1, s_2, s_n\}\\ G(W) &= \max~_{i:w_i\leq w} ~\{G(W-s_i) + v_i\}, G(0)=0\\ \end{align*}

I am not sure what does the marked text mean in this recurrence formula. Because I think $W$ is a variable not an array so $i\colon w_i<w$ does not really make sense to me. Could someone please explain this to me?

The notation is a crossover between

$\qquad\displaystyle \max_{i}$

and

$\qquad\displaystyle \max \{ \dots \mid i \}$.

It means the same as

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

guessing about the domain of $i$.

• now I wonder if on each i iteration W-si has to be lower than original W or previous iteration W-si-1 ? – zerociudo Apr 14 '18 at 12:54
• @zerociudo No, no such thing; there are just two conditions. You may want to read up on set notation, e.g. in the free Book of Proof. (This question was about notation. If you have questions about the ideas behind the recurrence, please post a new question.) – Raphael Apr 14 '18 at 13:27