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}$


$\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$.

| cite | improve this answer | |
  • $\begingroup$ now I wonder if on each i iteration W-si has to be lower than original W or previous iteration W-si-1 ? $\endgroup$ – zerociudo Apr 14 '18 at 12:54
  • $\begingroup$ @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.) $\endgroup$ – Raphael Apr 14 '18 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.