1
$\begingroup$

I have a recurrece equation

enter image description here

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?

Improve this question
$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$
    – Yuval Filmus
    Apr 14, 2018 at 14:06
  • $\begingroup$ @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 $\endgroup$
    – zerociudo
    Apr 14, 2018 at 14:14
  • $\begingroup$ 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$. $\endgroup$
    – Yuval Filmus
    Apr 14, 2018 at 14:18
  • $\begingroup$ The $w_i$, like the $s_i$ and $v_i$, are fixed and do not change during the recurrence. $\endgroup$
    – Yuval Filmus
    Apr 14, 2018 at 14:19
  • $\begingroup$ 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 $\endgroup$
    – zerociudo
    Apr 14, 2018 at 14:25

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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